A116537 a(1)=1. a(n) = number of positive integers that are < n, are coprime to n and do not occur among the first n-1 terms of the sequence.

1, 0, 1, 1, 3, 1, 4, 2, 3, 2, 6, 3, 7, 4, 4, 5, 9, 3, 10, 4, 7, 5, 13, 4, 12, 7, 11, 6, 16, 4, 17, 8, 10, 9, 12, 6, 21, 9, 14, 8, 23, 6, 24, 11, 13, 13, 27, 9, 25, 10, 19, 12, 30, 9, 22, 13, 21, 15, 33, 9, 34, 15, 21, 17, 27, 12, 39, 17, 28, 13, 41, 14, 42, 19, 24, 20, 36, 15, 45

Offset

1,5

Links

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

Example

The positive integers which are both less than 9 and are coprime to 9 are 1, 2, 4, 5, 7 and 8. Of these, only the three integers 5, 7 and 8 do not occur earlier in the sequence, so a(9)=3.

Prog

(Perl) #!/usr/bin/perl -w
use Math::PARI qw/ gcd eulerphi /;
$| = 1;
$n = 2;
%seen = (1 => 1);
while (1) {
$v = eulerphi($n) - grep gcd($n, $_) == 1, keys %seen;
$seen{$v} = 1;
++$n;
print "$v ";
} # from Hugo van der Sanden, Mar 30 2006

Crossrefs

Cf. A096216.

Sequence in context: A135822 A242111 A209919 * A194307 A346770 A048225

Adjacent sequences: A116534 A116535 A116536 * A116538 A116539 A116540

Keyword

nonn

Author

Leroy Quet, Mar 27 2006

Extensions

More terms from Hugo van der Sanden, Mar 31 2006

Status

approved