A048869 -id:A048869 - cp's OEIS frontend

A051250 Numbers whose reduced residue system consists of 1 and prime powers only.

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42, 60

Offset: 1

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

			RRS[ 60 ] = {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}.

M. Dalezman, From 30 to 60 Is Not Twice as Hard, Mathematics Magazine, Vol. 73, No. 2 (Apr. 2000), pp. 151-153.
O. Ore and N. J. Fine, Reduced Residue Systems, American Mathematical Monthly Vol. 66, No. 10 (Dec., 1959), pp. 926-927.

Cf. A048597, A048862-A048869.

Cf. A010055, A038566.

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

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 *)

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

A048982 Number of numbers which have a "prime-rich" reduced residue system (RRS) and binary order n.

Original entry on oeis.org

0, 0, 0, 1, 3, 8, 15, 22, 32, 50, 85, 80, 98, 84, 59, 37, 10, 2, 0, 0, 0

Offset: 0

Labos Elemer

It is remarkable that in exponentially increasing ranges these occurrences increase to n=13 and thereafter decline to zero. So A048868 is believed to be finite.

			In binary order (A029837) zone of 7, i.e., in [65,128], 22 numbers belong to A048868: 66, 68, 70, 72, 74, 76, 78, 80, 84, 88, 90, 96, 98, 100, 102, 104, 108, 110, 112, 114, 120, and 126. The largest term is 90090. The largest 4 are divisible by 2310, the largest 28 by 210, and the largest 103 by 30.

Cf. A048862, A048863, A048864, A048865, A048866, A048867, A048868, A048869.

Cf. A002110, A029837, A048597.

cp's OEIS Frontend

A051250 Numbers whose reduced residue system consists of 1 and prime powers only.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI