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

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051250 Numbers whose reduced residue system consists of 1 and prime powers only. 9
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42, 60 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

From Reinhard Zumkeller, 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)

The sequence is indeed finite. Let pi*(x) denote 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

LINKS

Table of n, a(n) for n=1..17.

O. Ore and N. J. Fine, Reduced Residue Systems, American Mathematical Monthly Vol. 66, No. 10 (Dec., 1959), pp. 926-927.

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, Jul 11 2011 *)

PROG

(Haskell)

a051250 n = a051250_list !! (n-1)

a051250_list = filter (all ((== 1) . a010055) . a038566_row) [1..]

-- Reinhard Zumkeller, May 27 2015, 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

Cf. A048597, A048862-A048869.

Cf. A010055, A038566.

Sequence in context: A172248 A082415 A005236 * A143071 A305759 A143513

Adjacent sequences:  A051247 A051248 A051249 * A051251 A051252 A051253

KEYWORD

nice,nonn,fini,full

AUTHOR

Labos Elemer

STATUS

approved

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 8 07:52 EST 2021. Contains 349593 sequences. (Running on oeis4.)