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

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

Author

Jianing Song, Feb 22 2021

Keywords

• nonn

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

• Chai Wah Wu, Table of n, a(n) for n = 1..100

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