A118657 a(n) = Sum_[k unrelated to n and k

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, 612, 1767, 0, 4267, 0, 7712, 5684, 15446, 6348, 37219, 0, 68111, 49245, 142588, 0, 340698, 0, 624999, 587477, 1244507, 0, 3131628, 348903, 6214474, 4172889, 11883510, 0, 28533958, 7586253, 52606134, 36932401, 104858718, 0, 259054161

Offset: 1

Author

Jonathan Vos Post, May 18 2006

Keywords

• easy
• nonn

Comments

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.

Examples

			a(6) = 1 because 4 is the only number less than 6 which is unrelated to 6, so a(6) = a(4) = 1.
a(10) = a(4) + a(6) + a(8) = 1 + 1 + 1 = 3.
a(12) = a(8) + a(9) + a(10) = 1 + 1 + 3 = 5.
		

Crossrefs

See also A045763 = number of numbers "unrelated to n": mA002033; A045545; A111356 = numbers n such that the number of numbers "unrelated to n" is itself unrelated to n.

Cf. A070297.

Programs

Mathematica

unr[n_, k_] := GCD[n, k] > 1 && Mod[n, k] > 0; a[1] = a[2] = a[3] = a[4] = 1;
a[n_] := a[n] = Sum[a[k] Boole[unr[n, k]], {k, n - 1}]; Array[a, 60]

Formula

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

Extensions

Edited by N. J. A. Sloane, Dec 03 2006

Edited and many terms corrected by Giovanni Resta, Jun 16 2016