%I #40 Nov 09 2023 08:53:25
%S 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,
%T 10,12,9,12,8,19,10,14,12,21,8,22,12,12,12,24,12,22,11,18,14,27,10,18,
%U 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
%N 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.
%C From _Jeffrey Shallit_, Jun 14 2018: (Start)
%C Except for first term, the same as A180783.
%C Equal to the number of elements x relatively prime to n such that x mod n >= x^(-1) mod n. (End)
%D Felix Weinstein, The Fibonacci Partitions, preprint, 1995.
%H F. V. Weinstein, <a href="https://arxiv.org/abs/math/0307150">Notes on Fibonacci partitions</a>, arXiv:math/0307150 [math.NT], 2003-2018.
%F 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
%e 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 + ...
%t 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 *)
%o (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);
%o a(n) = { my(f = factor(n)); prod(i=1, #f~, ap(f[i,1], f[i, 2]));} \\ _Michel Marcus_, Apr 19 2014
%o (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 */
%o (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 */
%Y Cf. A007896, A007898, A180783.
%K nonn,mult
%O 1,3
%A Felix Weinstein (wain(AT)ana.unibe.ch), Dec 11 1999
%E Definition corrected by _Michel Marcus_, Apr 19 2014
%E Changed name from phi(n) (which caused much confusion with the Euler phi-function) to a(n). - _N. J. A. Sloane_, May 26 2014