login
a(0) = 1; a(n) = Sum_{0 <= k < n and gcd(k,n) = 1} a(k).
12

%I #27 Feb 05 2022 16:16:43

%S 1,1,1,2,3,7,8,22,32,66,91,233,263,729,1038,2059,3119,7674,8666,24014,

%T 32741,68645,103219,252633,285313,755681,1111037,2292275,3335374,

%U 8284946,8570252,25140144,36829131,75778418,112599875,262721802

%N a(0) = 1; a(n) = Sum_{0 <= k < n and gcd(k,n) = 1} a(k).

%C a(n+2) = 2*a(n) + a(n+1) if and only if n is the lesser of a pair of twin primes (i.e., n is in A001359). - _Benoit Cloitre_, Nov 28 2002

%C Starting with offset 1 = row sums of triangle A143656. - _Gary W. Adamson_, Aug 28 2008

%H G. C. Greubel, <a href="/A045545/b045545.txt">Table of n, a(n) for n = 0..500</a>

%F Lim sup a(n+1)/a(n) = 3. - Jan Szejko (js248325(AT)students.mimuw.edu.pl), May 29 2010

%F Equals M * V where M = A054521 is an infinite lower triangular matrix and V = A045545 is a vector starting [1, 1, 2, 3, 7, 8, ...]. E.g., a(6) = 8 since the relative primes of 6 are 1 and 5 and a(1) + a(5) = 1 + 7 = 8. - _Gary W. Adamson_, Jan 13 2007

%p a := proc(n) local j; option remember;

%p if n <3 then 1;

%p else add(`if`(gcd(n, j) = 1, a(j), 0), j = 1 .. n - 1);

%p end if; end proc;

%p seq(a(n), n = 0 .. 30); # _G. C. Greubel_, Mar 08 2021

%t a[0] = 1; a[n_] := a[n] = Block[{k = 0, s = 0}, While[k < n, If[ GCD[n, k] == 1, s = s + a[k]]; k++ ]; s]; Table[ a[n], {n, 0, 35}] (* _Robert G. Wilson v_, Jun 09 2006 *)

%t a[n_]:= a[n]= If[n<3, 1, Sum[Boole[GCD[n,k]==1] a[k], {k,n-1}]]; Table[a[n], {n, 0, 40}] (* _G. C. Greubel_, Mar 08 2021 *)

%o (Sage)

%o @CachedFunction

%o def a(n):

%o if n<3: return 1

%o else: return sum( kronecker_delta(gcd(n,j),1)*a(j) for j in (0..n-1) )

%o [a(n) for n in (0..40)] # _G. C. Greubel_, Mar 08 2021

%Y Cf. A002033, A023896, A054251.

%Y Cf. A143656. - _Gary W. Adamson_, Aug 28 2008

%K nonn

%O 0,4

%A _David W. Wilson_