A007897 a(n) is multiplicative with a(2) = 1; a(4) = 2; a(2^i) = 2^(i-2)+2 if i>2; a(p^i) = 1+(p-1)*p^(i-1)/2 if prime p>2 and i>0.

1, 1, 2, 2, 3, 2, 4, 4, 4, 3, 6, 4, 7, 4, 6, 6, 9, 4, 10, 6, 8, 6, 12, 8, 11, 7, 10, 8, 15, 6, 16, 10, 12, 9, 12, 8, 19, 10, 14, 12, 21, 8, 22, 12, 12, 12, 24, 12, 22, 11, 18, 14, 27, 10, 18, 16, 20, 15, 30, 12, 31, 16, 16, 18, 21, 12, 34, 18, 24, 12, 36, 16, 37, 19, 22, 20, 24, 14, 40, 18, 28

Offset: 1

Author

Felix Weinstein (wain(AT)ana.unibe.ch), Dec 11 1999

Keywords

• nonn
• mult

Comments

From Jeffrey Shallit, Jun 14 2018: (Start)

Except for first term, the same as A180783.

Equal to the number of elements x relatively prime to n such that x mod n >= x^(-1) mod n. (End)

Examples

			G.f. = x + x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 2*x^6 + 4*x^7 + 4*x^8 + 4*x^9 + ...
		

References

• Felix Weinstein, The Fibonacci Partitions, preprint, 1995.

Links

• F. V. Weinstein, Notes on Fibonacci partitions, arXiv:math/0307150 [math.NT], 2003-2018.

Crossrefs

Cf. A007896, A007898, A180783.

Programs

Mathematica

a[ n_] := If[ n < 2, Boole[ n == 1],Times @@ Apply[ Function[ {p, e}, If[p == 2, If[e < 3, e, 2^(e - 2) + 2], 1 + p^(e - 1) (p - 1)/2]], FactorInteger @ n, 1]]; (* Michael Somos, May 26 2014 *)

PARI

ap(p, e) = if (p==2, if (e==1, 1, if (e==2, 2, 2^(e-2)+2)), 1+(p-1)*p^(e-1)/2);
a(n) = { my(f = factor(n)); prod(i=1, #f~, ap(f[i,1], f[i, 2]));} \\ Michel Marcus, Apr 19 2014

PARI

{a(n) = my(A, p, e); if( n<1, 0, A = factor(n); prod( k=1, matsize(A)[1], if( p = A[k,1], e = A[k,2]; if( p==2, if( e<3, e, 2^(e-2) + 2), 1 + p^(e-1) * (p-1) / 2))))}; /* Michael Somos, May 26 2014 */

PARI

{a(n) = if( n<1, 0, direuler( p = 2, n, if( p>2, 1 / (1 - X) + (p - 1) / 2 * X / (1 - p*X), (1 + X^2) / (1 - X) + p * X^3 / (1 - p*X))) [n])}; /* Michael Somos, May 26 2014 */

Formula

Dirichlet g.f.: zeta(s) * zeta(s-1) * ((2 - 2^(s+2) + 2^(2*s+1) - 1/2^(2*s-2))/(2^(2*s+1) - 3*2^s - 1)) * Product_{p prime} (1 - (1/p^(s-1) + 1/p^s - 1/p^(2*s-1) + 1/p^(2*s))/2). - Amiram Eldar, Nov 09 2023

Extensions

Definition corrected by Michel Marcus, Apr 19 2014

Changed name from phi(n) (which caused much confusion with the Euler phi-function) to a(n). - N. J. A. Sloane, May 26 2014