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

1, 1, 1, 2, 3, 7, 8, 22, 32, 66, 91, 233, 263, 729, 1038, 2059, 3119, 7674, 8666, 24014, 32741, 68645, 103219, 252633, 285313, 755681, 1111037, 2292275, 3335374, 8284946, 8570252, 25140144, 36829131, 75778418, 112599875, 262721802

Offset: 0

Author

David W. Wilson

Keywords

• nonn

Comments

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

Starting with offset 1 = row sums of triangle A143656. - Gary W. Adamson, Aug 28 2008

Links

• G. C. Greubel, Table of n, a(n) for n = 0..500

Crossrefs

Cf. A002033, A023896, A054251.

Cf. A143656. - Gary W. Adamson, Aug 28 2008

Programs

Maple

a := proc(n) local j; option remember;
if n <3 then 1;
else add(`if`(gcd(n, j) = 1, a(j), 0), j = 1 .. n - 1);
end if; end proc;
seq(a(n), n = 0 .. 30); # G. C. Greubel, Mar 08 2021

Mathematica

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 *)
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 *)

Sage

@CachedFunction
def a(n):
    if n<3: return 1
    else: return sum( kronecker_delta(gcd(n,j),1)*a(j) for j in (0..n-1) )
[a(n) for n in (0..40)] # G. C. Greubel, Mar 08 2021

Formula

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

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