login
a(n) = Sum_[k unrelated to n and k<n] a(k) = Sum_[k < n such that GCD(k,n) != 1 and k does not divide n ] a(k); a(1) = a(2) = a(3) = a(4) = 1.
0

%I #16 Jun 16 2016 22:21:56

%S 1,1,1,1,0,1,0,1,1,3,0,5,0,11,10,20,0,51,0,99,79,192,0,466,112,850,

%T 612,1767,0,4267,0,7712,5684,15446,6348,37219,0,68111,49245,142588,0,

%U 340698,0,624999,587477,1244507,0,3131628,348903,6214474,4172889,11883510,0,28533958,7586253,52606134,36932401,104858718,0,259054161

%N a(n) = Sum_[k unrelated to n and k<n] a(k) = Sum_[k < n such that GCD(k,n) != 1 and k does not divide n ] a(k); a(1) = a(2) = a(3) = a(4) = 1.

%C Primes include a(10) = 3, a(12) = 5, a(16) = 19, a(24) = 397. a(n) is unrelated to n for a(14) = 10, a(15) = 10, a(18) = 39, a(20) = 85, a(21) = 66, a(22) = 164.

%F For primes p>3, a(p) = 0.

%e a(6) = 1 because 4 is the only number less than 6 which is unrelated to 6, so a(6) = a(4) = 1.

%e a(10) = a(4) + a(6) + a(8) = 1 + 1 + 1 = 3.

%e a(12) = a(8) + a(9) + a(10) = 1 + 1 + 3 = 5.

%t unr[n_, k_] := GCD[n, k] > 1 && Mod[n, k] > 0; a[1] = a[2] = a[3] = a[4] = 1;

%t a[n_] := a[n] = Sum[a[k] Boole[unr[n, k]], {k, n - 1}]; Array[a, 60]

%Y See also A045763 = number of numbers "unrelated to n": m<n such that m is neither a divisor of n nor relatively prime to n; A002033; A045545; A111356 = numbers n such that the number of numbers "unrelated to n" is itself unrelated to n.

%Y Cf. A070297.

%K easy,nonn

%O 1,10

%A _Jonathan Vos Post_, May 18 2006

%E Edited by _N. J. A. Sloane_, Dec 03 2006

%E Edited and many terms corrected by _Giovanni Resta_, Jun 16 2016