|
%I #32 Apr 25 2016 12:00:14
%S 1,1,2,2,4,2,6,2,7,3,10,3,12,4,9,6,16,3,18,7,10,8,22,4,22,8,18,6,28,4,
%T 30,8,19,9,28,5,36,10,25,10,40,5,42,13,22,14,46,9,42,12,33,15,52,9,40,
%U 16,35,19,58,7,60,21,33,23,49,14,66,25,42,15,70,15,72,28,34,26,55,15,78
%N a(n) = number of terms among {a(1), a(2), a(3), ..., a(n-1)} that are coprime to n; a(1)=1.
%C A family of related sequences can be generated using different positive integers for a(1).
%H Peter Kagey, <a href="/A096216/b096216.txt">Table of n, a(n) for n = 1..10000</a>
%F If, for a given fixed a(1), b(n,j) = number of a(k)'s which are multiples of j, for 1 <= k <= n-1, then: a(n) = Sum_{j|n} mu(j)*b(n,j), where mu(j) is the Moebius (Möbius) function.
%e a(1)=1, a(2)=1 and a(9)=7 are those terms, prior to a(10), which are coprime with 10. So a(10) = 3.
%p a[1]:=1: for n from 2 to 100 do B:=[seq(gcd(n,a[j]),j=1..n-1)]; s:=0: for i from 1 to n-1 do if B[i]=1 then s:=s+1 else s:=s: fi: od: a[n]:=s: od: seq(a[n],n=1..85); # _Emeric Deutsch_, Aug 01 2005
%t a[1] = 1; a[n_] := a[n] = Count[ GCD[ Table[ a[i], {i, n - 1}], n], 1]; Table[ a[n], {n, 80}] (* _Robert G. Wilson v_, Jul 30 2004 *)
%o (Perl) #!/usr/bin/perl -w
%o use bigint; # only because it is an easy way to get gcd()
%o $| = $n = 1;
%o @a = (0);
%o while (1) {
%o $v = grep $n->bgcd($_) == 1, @a;
%o print $a[ $n++ ] = $v, " ";
%o } # _Hugo van der Sanden_, Mar 30 2006
%o (PARI) lista(nn) = {va = vector(nn); print1(va[1]=1, ", "); for (n=2, nn, va[n] = sum(k=1, n-1, gcd(va[k], n) == 1); print1(va[n], ", "););} \\ _Michel Marcus_, Apr 10 2016
%Y Cf. A056149, A116537.
%K nonn
%O 1,3
%A _Leroy Quet_, Jul 28 2004
%E Edited and extended by _Robert G. Wilson v_, Jul 30 2004
|
