cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A307437 a(n) is the smallest k such that 2n divides psi(k), psi = A002322.

Original entry on oeis.org

3, 5, 7, 17, 11, 13, 29, 17, 19, 25, 23, 73, 53, 29, 31, 97, 103, 37, 191, 41, 43, 89, 47, 97, 101, 53, 81, 113, 59, 61, 311, 193, 67, 137, 71, 73, 149, 229, 79, 187, 83, 203, 173, 89, 181, 235, 283, 97, 197, 101, 103, 313, 107, 109, 121, 113, 229, 233, 709, 241
Offset: 1

Views

Author

Jianing Song, Apr 08 2019

Keywords

Comments

a(n) exists for all n: by Dirichlet's theorem on arithmetic progressions, there exists a prime p congruent to 1 modulo 2n, so 2n divides psi(p) = p - 1.
a(n) is the smallest k such that (Z/kZ)* contains C_(2n) as a subgroup, where (Z/kZ)* is the multiplicative group of integers modulo n.
a(n) is the smallest k such that there exists some x such that ord(x,k) = 2n, where ord(x,k) is the multiplicative order of x modulo k.
Record values of a(n)/n occur at n = 1, 4, 12, 19, 59, 167, 196, 197, 227, 317, 457, 521, 706, ... (A341888).
From Jianing Song, Feb 21 2021: (Start)
a(n) is bounded above by (2n)^2 since n divides psi(n^2).
a(n) is usually odd. There are only 7 values <= 10^4 for n such that a(n) is even, namely n = 256, 512, 1024, 2816, 4096, 5632 and 8192 (A341887). (End)
a(n) is odd or divisible by 16, since psi(k) = psi(2k) = psi(4k) = psi(8k) for odd k > 1. - Jianing Song, Feb 22 2021

Examples

			For n = 7, psi(29) = 28 and 29 is the smallest k such that 14 divides psi(k), so a(7) = 29.
For n = 27, psi(81) = 54 and 81 is the smallest k such that 54 divides psi(k), so a(27) = 81.
For n = 40, psi(187) = 80 and 187 is the smallest k such that 80 divides psi(k), so a(40) = 187.
For n = 42, psi(203) = 84 and 203 is the smallest k such that 84 divides psi(k), so a(42) = 203.

Links

Crossrefs

Cf. A002322, A307436, A341887, A341888.

Programs

  • Maple
    N:= 100: # for a(1)..a(N)
V:= Vector(N): count:= 0:
for k from 3 while count < N do
  S:= select(t -> t <= N and V[t]=0, numtheory:-divisors(numtheory:-lambda(k)/2));
  if nops(S) > 0 then count:= count + nops(S); V[convert(S,list)]:= k fi
od:
convert(V,list); # Robert Israel, Jul 10 2019
  • PARI
    a(n) = my(i=1); while(A002322(i)%(2*n), i++); i \\ See A002322 for its program
  • Python
    from sympy import reduced_totient
def A307437(n):
    k = 1
    while reduced_totient(k) % (2*n):
        k += 1
    return k # Chai Wah Wu, Feb 24 2021

Formula

From Jianing Song, Feb 26 2021: (Start)
For odd prime p, a((p-1)/2*p^e) = p^(e+1) if (p-1)*p^e+1 is composite, (p-1)*p^e+1 otherwise. Proof: suppose a((p-1)/2*p^e) = p^a*r < p^(e+1), p does not divide r, then (p-1)*p^e | lcm((p-1)*p^(a-1), psi(r)) => p^e | lcm(p^(a-1), psi(r)).
If p^e | p^(a-1), then a((p-1)/2*p^e) >= p^a >= p^(e+1).
If p^e does not divide p^(a-1), then p^e | psi(r). r must have a prime factor of the form q = 2*t*p^e+1. If a >= 1, then a((p-1)/2*p^e) >= p*(2*p^e+1) > p^(e+1). So we must have a = 0. Write r = r'*q^b, then p-1 | lcm(psi(r'), 2*t*p^e*q^(b-1)) => p-1 | lcm(psi(r'), 2*t), hence 2*t*r' >= 2*t*psi(r') >= lcm(psi(r'), 2*t) => p-1. If 2*t*r' > p-1, then a((p-1)/2*p^e) >= r'*q = r'*(2*t*p^e+1) > p^(e+1). If 2*t*r' = p-1, then r' = psi(r') => r' = 1, 2*t = p-1, hence (p-1)*p^e+1 is prime. (End)

A341886 Numbers k such that the smallest m such that k | psi(m) is even, psi = A002322.

Original entry on oeis.org

512, 1024, 2048, 5632, 8192, 11264, 16384, 22528, 54272, 57856, 97792, 108544, 122368, 131072, 150016, 165376, 169984, 180224, 188928, 195584, 210432, 244736, 248320, 256000, 276480, 279040, 300032, 317440, 333312, 334336, 335872, 337408, 352256, 367616, 371712
Offset: 1

Views

Author

Jianing Song, Feb 22 2021

Keywords

Comments

Even k such that A307437(k/2) is even. Note that k must be divisible by 4.
Write k = r*2^e with odd r. Let s be the smallest odd number such that k | psi(s), t be the smallest number such that r | psi(t), v2(psi(t)) = a, then k is a term <=> a < e, t*2^(e+2) < s, where v2 = A007814 is the 2-adic valuation.
Proof: Let m be the smallest number such that k | psi(k).
"<=" If m is odd, then m >= s > t*2^(e+2), but k | psi(t*2^(e+2)), contradicting with minimality of m.
"=>" If a >= e, then m = t is odd. Write m = l*2^b, b >= 4, l odd, then k | lcm(psi(l), 2^(b-2)) => r | psi(l) => l >= t. If(v2(psi(l))) < b-2, then b-2 >= e => t*2^(e+2) <= l*2^b = m < s. If(v2(psi(l))) > b-2, then k | psi(l), contradicting with minimality of m. QED.
A special case: suppose k = p*2^e where p is an odd prime. Let q be the smallest number such that p | psi(q), suppose that q = p*2^a*l + 1 < p^2, l odd. Then k is a term <=> a < e; t*2^e + 1 is composite for t = 1, 2, 3; t'*p*2^e + 1 is composite for t < 4*q/p.
Let s be the smallest odd number such that k | psi(s), then k is a term <=> a < e, q*2^(e+2) < s. Suppose that a < e, there are two cases:
(i) s = (p_1)^(e_1)*(p_2)^(e_2), p | psi((p_1)^(e_1)), 2^e | psi((p_2)^(e_2)). Since a < e, p_2 != q, so (p_1)^(e_1) = q, s = q*(t*2^e + 1) with t*2^e + 1 prime.
(ii) s = (p_1)^(e_1), n | psi((p_1)^(e_1)), so s = t'*p*2^e + 1 with t'*p*2^e + 1 prime.
Hence q*2^(e+2) < s <=> t*2^e + 1 is composite for t = 1, 2, 3; t'*p*2^e + 1 is composite for t < 4*q/p. QED.
2^e is a term <=> t*2^e + 1 is composite for t = 1, 2, 3. It follows that this sequence is infinite.
3*2^e is a term <=> t*2^e + 1 is composite for t = 1, 2, 3, 6, 9, 12, 15, 18, 21, 24, 27.
From Jianing Song, Feb 27 2021: (Start)
All terms are divisible by 512. Proof: Write a term k = 2^a*r > 2 with odd r. Suppose the smallest m such that k divides psi(m) is m = 2^e*s with odd s, e >= 1.
i) a <= 1. If s = 1, then k = r divides psi(2^e) => k <= 2r = 2, a contradiction. Hence s > 1, then k = r or 2r divides psi(s).
ii) a = 2. If s has a prime factor congruent to 1 modulo 3, then r | psi(s) => k = 4r divides psi(s). Otherwise, we must have 4 | psi(2^e) => e >= 4, then k = 4r divides psi(5*s), a contradiction.
iii) a = 3. If s has a prime factor congruent to 1 modulo 8, then r | psi(s) => k = 8r divides psi(s). Otherwise, we must have 8 | psi(3^e) => e >= 5, then k = 8r divides psi(17*s), a contradiction.
The cases a = 4, 5, 6, 7, 8 are similar. (End)

Examples

			psi(2048) = 512 is divisible by 512 = 2^9, and there is no odd m < 2048 such that 512 | psi(m), so 512 is a term. Also, 512 is a term since 1*512 + 1 = 513 = 3^3 * 19, 2*512 + 1 = 1025 = 5^2 * 41, 3*512 + 1 = 1537 = 29 * 53 are all composite.
psi(47104) = 5632 is divisible by 5632 = 11*2^9, and there is no m < 47104 such that 5632 | psi(m), so 5632 is a term. Also, 5632 is a term since t*512 + 1 is composite for t = 1, 2, 3; t*5632 + 1 is composite for t < 4*23/11 (t <= 8).

Links

Crossrefs

Cf. A002322, A307437, A341887, A007814.

Programs

  • PARI
    forstep(n=2, 10000, 2, if(A307437(n)%2==0, print1(2*n, ", "))) \\ see A307437 for its program

Formula

a(n) = A341887(n)*2.

Extensions

More terms from Chai Wah Wu, Feb 25 2021

A342037 Numbers k such that A307437(k) is divisible by 3.

Original entry on oeis.org

1, 27, 702, 1107, 1431, 2187, 3375, 3456, 4266, 5157, 5805, 6561, 6831, 7668, 8073, 11313, 11961, 12771, 12825, 13149, 13176, 13257, 14526, 14715, 14796, 15039, 16011, 16227, 16497, 17388, 17496, 17631, 19251, 19332, 19413, 20223, 20277, 20871, 20952, 21654
Offset: 1

Views

Author

Jianing Song, Feb 26 2021

Keywords

Comments

Indices of terms of A307437 that is divisible by 3.
For e > 0, 3^e is a term if and only if 2*3^e+1 is composite. Hence this sequence is infinite.
All terms > 1 are divisible by 27. Proof: Write a term k = 3^a*r > 1, 3 does not divide r. Suppose A307437(k) = 3^e*s, 3 does not divide s, e >= 1.
i) a = 0. If s = 1, then 2k = 2r divides psi(3^e) = 2*3^(e-1) => k = r = 1, a contradiction. Hence s > 1, then 2k = 2r divides psi(s).
ii) a = 1. If s has a prime factor congruent to 1 modulo 3, then r | psi(s) => 2k = 6r divides psi(s). Otherwise, we must have 3 | psi(3^e) => e >= 2, then 2k = 6r divides psi(7*s), a contradiction.
iii) a = 2. If s has a prime factor congruent to 1 modulo 9, then r | psi(s) => 2k = 18r divides psi(s). Otherwise, we must have 9 | psi(3^e) => e >= 3, then 2k = 18r divides psi(19*s), a contradiction.

Examples

			The smallest k such that 2*702 | psi(k) is k = 4293 = 3^4 * 53, hence 702 is a term.
The smallest k such that 2*3375 | psi(k) is k = 20331 = 3^4 * 251, hence 3375 is a term.
The smallest k such that 2*3456 | psi(k) is k = 20817 = 3^4 * 257, hence 3456 is a term.

Links

Crossrefs

Cf. A307437, A341887, A003306.

Programs

  • PARI
    print1("1, "); forstep(n=27, 10000, 27, if(A307437(n)%3==0, print1(n, ", "))) \\ see A307437 for its program

Extensions

More terms from Chai Wah Wu, Feb 27 2021
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.