A124385 For all n >= 2, Sum_{2<=k<=n, gcd(k,n)>1} a(k) = 1. a(1)=1.

1, 1, 1, 0, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -3, 1, 1, 1, 1, 1, -3, -1, 3, 5, -1, 1, -7, 1, 9, 5, -1, 5, -13, 1, 13, 11, -5, 1, -25, 1, 25, 29, 5, 1, -53, 19, 19, 53, 23, 1, -95, -73, 81, 81, 25, 1, -119, 1, 119, 27, 1, 113, -143, 1, 89, 243, -69, 1, -335, 1, 457, 351, -81, 145, -841, 1, 497, 831, 425, 1, -1809, -883, 1809

Offset

1,18

Links

Antti Karttunen, Table of n, a(n) for n = 1..10000

Formula

a(1) = 1, and for n > 1, a(n) = 1 - Sum_{2 <= k <= n-1} [gcd(k,n)>1]*a(k), where [ ] is the Iverson bracket. - Antti Karttunen, Feb 22 2023

Example

The positive integers which are <= 6 and are not coprime to 6 are 2,3,4,6. And a(6) is such that a(2)+a(3)+a(4)+a(6) = 1, i.e. a(6) = 1 - (a(2)+a(3)+a(4)) = 1 - 2 = -1.
The positive integers which are <= 12 and are not coprime to 12 2,3,4,6,8,9,10,12. And a(12) is such that a(2)+a(3)+a(4)+a(6)+a(8)+a(9)+a(10)+a(12) = 1.

Mathematica

f[n_] := Select[Range[2, n], GCD[ #, n] > 1 &]; g[l_] :=Append[l, 1 - Plus @@ l[[Most[f[Length[l] + 1]]]]]; Nest[g, {1}, 85] (* Ray Chandler, Nov 13 2006 *)

Prog

(PARI)
up_to_n = 10000;
A124385list(up_to_n) = { my(v=vector(up_to_n)); v[1] = 1; for(n=2, up_to_n, v[n] = 1-sum(k=2, n-1, (gcd(k, n)>1)*v[k])); (v); };
v124385 = A124385list(up_to_n);
A124385(n) = v124385[n]; \\ Antti Karttunen, Feb 22 2023

Crossrefs

Cf. A124386.

Sequence in context: A061680 A355456 A097558 * A317624 A328575 A106478

Adjacent sequences: A124382 A124383 A124384 * A124386 A124387 A124388

Keyword

sign

Author

Leroy Quet, Oct 29 2006

Extensions

Extended by Ray Chandler, Nov 13 2006

Status

approved