|
|
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
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
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)
|
|
REFERENCES
|
Felix Weinstein, The Fibonacci Partitions, preprint, 1995.
|
|
LINKS
|
|
|
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
|
|
EXAMPLE
|
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 + ...
|
|
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 *)
|
|
PROG
|
(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 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,mult
|
|
AUTHOR
|
Felix Weinstein (wain(AT)ana.unibe.ch), Dec 11 1999
|
|
EXTENSIONS
|
Changed name from phi(n) (which caused much confusion with the Euler phi-function) to a(n). - N. J. A. Sloane, May 26 2014
|
|
STATUS
|
approved
|
|
|
|