cp's OEIS Frontend

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

%I A045545 #27 Feb 05 2022 16:16:43
%S A045545 1,1,1,2,3,7,8,22,32,66,91,233,263,729,1038,2059,3119,7674,8666,24014,
%T A045545 32741,68645,103219,252633,285313,755681,1111037,2292275,3335374,
%U A045545 8284946,8570252,25140144,36829131,75778418,112599875,262721802
%N A045545 a(0) = 1; a(n) = Sum_{0 <= k < n and gcd(k,n) = 1} a(k).
%C A045545 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 A045545 Starting with offset 1 = row sums of triangle A143656. -  _Gary W. Adamson_, Aug 28 2008
%H A045545 G. C. Greubel, <a href="/A045545/b045545.txt">Table of n, a(n) for n = 0..500</a>
%F A045545 Lim sup a(n+1)/a(n) = 3. - Jan Szejko (js248325(AT)students.mimuw.edu.pl), May 29 2010
%F A045545 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 A045545 a := proc(n) local j; option remember;
%p A045545 if n <3 then 1;
%p A045545 else add(`if`(gcd(n, j) = 1, a(j), 0), j = 1 .. n - 1);
%p A045545 end if; end proc;
%p A045545 seq(a(n), n = 0 .. 30); # _G. C. Greubel_, Mar 08 2021
%t A045545 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 A045545 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 A045545 (Sage)
%o A045545 @CachedFunction
%o A045545 def a(n):
%o A045545     if n<3: return 1
%o A045545     else: return sum( kronecker_delta(gcd(n,j),1)*a(j) for j in (0..n-1) )
%o A045545 [a(n) for n in (0..40)] # _G. C. Greubel_, Mar 08 2021
%Y A045545 Cf. A002033, A023896, A054251.
%Y A045545 Cf. A143656. - _Gary W. Adamson_, Aug 28 2008
%K A045545 nonn
%O A045545 0,4
%A A045545 _David W. Wilson_