The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 4

%I

%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.

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 19 10:30 EDT 2021. Contains 343112 sequences. (Running on oeis4.)