

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.


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



