login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

A067133
n is a term if the phi(n) numbers in [0,n-1] and coprime to n form an arithmetic progression.
2
1, 2, 3, 4, 5, 6, 7, 8, 11, 13, 16, 17, 19, 23, 29, 31, 32, 37, 41, 43, 47, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241
OFFSET
1,2
COMMENTS
The sequence consists of primes, powers of 2 and 6. Sketch of proof: Let k be the common difference of the arithmetic progression. If n is odd, then 1 and 2 are coprime to n, so k=1 and n is prime. If n==0 (mod 4), then n/2-1 and n/2+1 are coprime to n, so k=2 and n is a power of 2. If n==2 (mod 4), then n/2-2 and n/2+2 are coprime to n, so k divides 4 and n is either 2 or 6.
From Bernard Schott, Jan 08 2021: (Start)
This sequence is the answer to the 2nd problem, proposed by Romania, during the 32nd International Mathematical Olympiad in 1991 at Sigtuna (Sweden) (see the link IMO Compendium and reference Kuczma).
These phi(m) numbers coprimes to m form an arithmetic progression with at least 3 terms iff m = 5 or m >= 7. (End)
REFERENCES
Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 6 and 61-62.
EXAMPLE
8 is a term as phi(8) = 4 and the coprime numbers 1,3,5,7 form an arithmetic progression. 17 is a member as phi(17) = 16 and the numbers 1 to 16 form an arithmetic progression.
MATHEMATICA
rps[ n_ ] := Select[ Range[ 0, n-1 ], GCD[ #, n ]==1& ]; difs[ n_ ] := Drop[ n, 1 ]-Drop[ n, -1 ]; Select[ Range[ 1, 250 ], Length[ Union[ difs[ rps[ # ] ] ] ]<=1& ]
PROG
(PARI) isok(n) = {my(v = select(x->gcd(x, n)==1, [1..n]), dv = vector(#v-1, k, v[k+1] - v[k])); if (#dv, if (vecmin(dv) != vecmax(dv), return(0))); return(1)} \\ Michel Marcus, Jan 08 2021
(Python)
from sympy import primepi
def A067133(n):
def bisection(f, kmin=0, kmax=1):
while f(kmax) > kmax: kmax <<= 1
while kmax-kmin > 1:
kmid = kmax+kmin>>1
if f(kmid) <= kmid:
kmax = kmid
else:
kmin = kmid
return kmax
def f(x): return int(n+x-(x>5)+(0 if x<=1 else 1-primepi(x))-x.bit_length())
return bisection(f, n, n) # Chai Wah Wu, Sep 19 2024
CROSSREFS
Equals A000040 U A000079 U {6}.
Equals A174090 U {6}.
Sequence in context: A084369 A167211 A362095 * A192588 A351914 A258946
KEYWORD
easy,nonn
AUTHOR
Amarnath Murthy, Jan 09 2002
EXTENSIONS
Edited by Dean Hickerson, Jan 15 2002
STATUS
approved