A108514 If n is a power of 2, a(n)=n; otherwise a(n) = (p-1)*n/p where p = smallest odd prime divisor of n.

1, 2, 2, 4, 4, 4, 6, 8, 6, 8, 10, 8, 12, 12, 10, 16, 16, 12, 18, 16, 14, 20, 22, 16, 20, 24, 18, 24, 28, 20, 30, 32, 22, 32, 28, 24, 36, 36, 26, 32, 40, 28, 42, 40, 30, 44, 46, 32, 42, 40, 34, 48, 52, 36, 44, 48, 38, 56, 58, 40, 60, 60, 42, 64, 52, 44, 66, 64, 46, 56, 70, 48, 72, 72, 50

Offset: 1

Author

S. Muthukrishnan (muthu(AT)research.att.com), Jun 23 2005

Keywords

• nonn

Links

• David A. Corneth, Table of n, a(n) for n = 1..10000
• Z. Nedev, A Reduced Computational Complexity Strategy for the Magnus-Derek Game, International Mathematical Forum, Vol. 9, 2014, no. 7, pp. 325 - 333. See p. 326.
• Z. Nedev and S. Muthukrishnan, The Nagger-Mover Game, DIMACS Tech. Report 2005-22.

Crossrefs

Cf. A108738.

Programs

Maple

with(numtheory): a:=proc(n) local nn: nn:=factorset(n): if n=1 then 1 elif nn={2} then n elif nn[1]=2 then (nn[2]-1)*n/nn[2] else (nn[1]-1)*n/nn[1] fi end:

Mathematica

Array[If[IntegerQ@ Log2@ #1, #1, #1 (#2 - 1)/#2] & @@ {#, SelectFirst[FactorInteger[#][[All, 1]], # > 2 &]} &, 75] (* Michael De Vlieger, Oct 25 2017 *)

PARI

first(n) = {my(res = vector(n, i, i)); forprime(p = 3, n, for(k = 1, n\p, if(res[k*p] == k*p, res[k*p]*=(p-1)/p))); res} \\ David A. Corneth, Oct 25 2017

Extensions

Definition revised by N. J. A. Sloane, Oct 28 2017 at the suggestion of Michel Marcus.