login
Very round numbers: reduced residue system consists of only primes and 1.
30

%I #63 Sep 06 2024 17:28:10

%S 1,2,3,4,6,8,12,18,24,30

%N Very round numbers: reduced residue system consists of only primes and 1.

%C According to Ribenboim, Schatunowsky and Wolfskehl independently showed that 30 is the largest element in the sequence. This gives a lower bound for the maximum of the smallest prime in a, a+d, a+2d, ... taken over all a with 1 < a < d and gcd(a,d) = 1 for d > 30 [see Ribenboim].

%C It appears that 2, 4, 6, 10, 12 are all the numbers n with the property that every number m in the range n < m < 2n that is coprime to n is also prime. - _Ely Golden_, Dec 05 2016

%C Golden's guess is true. See a proof in the links section. - _FUNG Cheok Yin_, Jun 19 2021

%D A. H. Beiler, Recreations in the Theory of Numbers, page 91.

%D H. Rademacher and O. Toeplitz, Von Zahlen und Figuren, Springer Verlag, Berlin, 1933, Zweite Auflage, see last chapter.

%D H. Rademacher & O. Toeplitz, The Enjoyment of Mathematics, pp. 187-192 Dover Publications, NY 1990.

%D P. Ribenboim, The little book of big primes, Chapter on primes in arithmetic progression.

%D J. E. Roberts, Lure of Integers, pp. 179-180 MAA 1992.

%D J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 89.

%D David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 111.

%H H. Bonse, <a href="https://archive.org/stream/archivdermathem31unkngoog#page/n307/mode/2up">Über eine bekannte Eigenshaft der Zahl 30 und ihre Verallgemeinerung</a>, Archiv d. Math. u. Physik (3) vol. 12 (1907) 292-295.

%H Ross Honsberger, <a href="https://www.jstor.org/stable/3026742">Mathematical Gems</a>, The Two-Year College Mathematics Journal, Vol. 10, No. 3 (Jun., 1979), pp. 195-197 (3 pages).

%H Ross Honsberger, <a href="https://archive.org/details/MathematicalDiamonds/page/n87/mode/2up">Two distinguished integers</a>, in Mathematical Diamonds, MAA, 2003, see p. 79. [Added by _N. J. A. Sloane_, Jul 05 2009]

%H Bill Taylor, <a href="http://mathforum.org/epigone/sci.math/chaxclixsnerm">Posting to sci.math, Sep 13 1999</a> [Broken link]

%H Fung Cheok Yin, <a href="http://oeis.org/wiki/User:FUNG_Cheok_Yin/proof(i)_A048597">A property of the set "2, 4, 6, 10, 12"</a>, Dec 24 2020.

%e The reduced residue systems of these numbers are as follows: {{1, {1}}, {2, {1}}, {3, {1, 2}}, {4, {1, 3}}, {6, {1, 5}}, {8, {1, 3, 5, 7}}, {12, {1, 5, 7, 11}}, {18, {1, 5, 7, 11, 13, 17}}, {24, {1, 5, 7, 11, 13, 17, 19, 23}}, {30, {1, 7, 11, 13, 17, 19, 23, 29}}}.

%t Select[Range[10^3], Function[n, Times @@ Boole@ Map[Or[# == 1, PrimeQ@ #] &, Select[Range@ n, CoprimeQ[#, n] &]] == 1]] (* _Michael De Vlieger_, Dec 13 2016 *)

%o (PARI) is(n)=forcomposite(k=2,n-1,if(gcd(n,k)==1, return(0))); 1 \\ _Charles R Greathouse IV_, Apr 28 2015

%Y The sequences consists of the n with A036997(n)=0.

%K fini,full,nonn

%O 1,2

%A _Labos Elemer_

%E Additional comments from Ulrich Schimke (ulrschimke(AT)aol.com), May 29 2001