OFFSET
1,3
COMMENTS
Every positive integer occurs. Proof: it suffices to show that every prime number occurs infinitely many times in {a(prime(m)):m>=1}. Given prime p = prime(i), by Dirichlet's theorem on arithmetic progressions, there exist infinitely many primes congruent to 1 modulo 2^i but not 2^(i+1), hence the result.
For example, take n = 2*3^2*5^3. Note that a(3) = 2, a(5) = a(13) = 3, a(41) = a(73) = a(89) = 5, so a(3*5*13*41*73*89) = n.
LINKS
Jianing Song, Table of n, a(n) for n = 1..10000
FORMULA
Multiplicative with a(2) = 1, a(4) = 2, a(2^e) = 2*prime(e-2) for e >= 3; a(p^e) = prime(v(p-1,2)), where v(,2) is the 2-adic valuation.
EXAMPLE
(Z/80Z)* = C_2 X C_4 X C_4, so a(80) = prime(1)*prime(2)*prime(2) = 18.
(Z/85Z)* = C_4 X C_16, so a(85) = prime(2)*prime(4) = 21.
MATHEMATICA
f[p_, e_] := If[p == 2, Switch[e, 1, 1, 2, 2, _, 2*Prime[e-2]], Prime[IntegerExponent[p-1, 2]]]; a[n_] := Times @@ f @@@ FactorInteger[n]; a[1] = 1; Array[a, 100] (* Amiram Eldar, Aug 30 2023 *)
PROG
(PARI) a(n) = my(L=znstar(n)[2]); factorback(vector(#L, i, prime(valuation(L[i], 2))))
CROSSREFS
KEYWORD
nonn,easy,mult
AUTHOR
Jianing Song, Aug 13 2023
STATUS
approved