A118657 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.

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,10

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.

Links

Table of n, a(n) for n=1..60.

Formula

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

Example

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.

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]

Crossrefs

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.

Cf. A070297.

Sequence in context: A051704 A049689 A227901 * A047760 A276908 A242246

Adjacent sequences: A118654 A118655 A118656 * A118658 A118659 A118660

Keyword

easy,nonn

Author

Jonathan Vos Post, May 18 2006

Extensions

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

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

Status

approved