login
This site is supported by donations to The OEIS Foundation.

 

Logo


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 October 21 06:39 EDT 2019. Contains 328292 sequences. (Running on oeis4.)