|
| |
|
|
A051250
|
|
Numbers whose reduced residue system consists of 1 and prime powers only.
|
|
8
| |
|
|
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42, 60
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Contribution from Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Oct 27 2010: (Start)
Conjecture: the sequence is finite and 60 is the largest term, empirically verified up to 10^7;
A139555(a(n)) = A000010(a(n)). (End)
Let pi*(x) count the number of prime powers (including 1) up to x. Dusart's bounds plus finite checking [up to 60184] shows that pi*(x) <= x/(log(x) - 1.1) + sqrt(x) for x >= 4. phi(n) > n/(e^gamma log log n + 3/(log log n)) for n >= 3. Convexity plus finite checking [up to 1096] allows a quick proof that phi(n) > pi*(n) for n > 420. So if n > 420, the reduced residue system mod n must contain at least one number that is neither 1 nor a prime power. Hence 60 is the last term in the sequence. [Charles R Greathouse IV, Jul 14 2011]
|
|
|
EXAMPLE
| RRS[ 60 ] = {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}.
|
|
|
MATHEMATICA
| fQ[n_] := Union[# == 1 || Mod[#, # - EulerPhi[#]] == 0 & /@ Select[ Range@ n, GCD[#, n] == 1 &]] == {True}; Select[ Range@ 100, fQ] (* Robert G. Wilson v, July 11 2011 *)
|
|
|
PROG
| (Haskell)
a051250 n = a051250_list !! (n-1)
a051250_list = filter (all (== 1) . map a010055 . totatives) [1..] where
totatives x = filter ((== 1) . (gcd x)) [1..x]
-- Reinhard Zumkeller, Dec 18 2011, Oct 27 2010
(PARI) isprimepower(n)=ispower(n, , &n); isprime(n)
is(n)=for(k=2, n-1, if(gcd(n, k)==1&&!isprimepower(k), return(0))); 1 \\ Charles R Greathouse IV, Jul 14 2011
|
|
|
CROSSREFS
| A048597, A048862-A048869.
Sequence in context: A172248 A082415 A005236 * A143071 A143513 A062849
Adjacent sequences: A051247 A051248 A051249 * A051251 A051252 A051253
|
|
|
KEYWORD
| nice,nonn,fini,full
|
|
|
AUTHOR
| Labos E. (labos(AT)ana.sote.hu)
|
| |
|
|
