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

%I #40 Dec 09 2023 04:08:44

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

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

%C From _Reinhard Zumkeller_, Oct 27 2010: (Start)

%C Conjecture: the sequence is finite and 60 is the largest term, empirically verified up to 10^7;

%C A139555(a(n)) = A000010(a(n)). (End)

%C 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

%H M. Dalezman, <a href="https://www.jstor.org/stable/2691088">From 30 to 60 Is Not Twice as Hard</a>, Mathematics Magazine, Vol. 73, No. 2 (Apr. 2000), pp. 151-153.

%H O. Ore and N. J. Fine, <a href="http://www.jstor.org/stable/2309817">Reduced Residue Systems</a>, American Mathematical Monthly Vol. 66, No. 10 (Dec., 1959), pp. 926-927.

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

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

%o (Haskell)

%o a051250 n = a051250_list !! (n-1)

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

%o -- _Reinhard Zumkeller_, May 27 2015, Dec 18 2011, Oct 27 2010

%o (PARI) isprimepower(n)=ispower(n,,&n);isprime(n)

%o is(n)=for(k=2,n-1,if(gcd(n,k)==1&&!isprimepower(k),return(0)));1 \\ _Charles R Greathouse IV_, Jul 14 2011

%Y Cf. A048597, A048862-A048869.

%Y Cf. A010055, A038566.

%K nice,nonn,fini,full

%O 1,2

%A _Labos Elemer_