cp's OEIS Frontend

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

%I A341886 #28 Jan 01 2024 11:56:24
%S A341886 512,1024,2048,5632,8192,11264,16384,22528,54272,57856,97792,108544,
%T A341886 122368,131072,150016,165376,169984,180224,188928,195584,210432,
%U A341886 244736,248320,256000,276480,279040,300032,317440,333312,334336,335872,337408,352256,367616,371712
%N A341886 Numbers k such that the smallest m such that k | psi(m) is even, psi = A002322.
%C A341886 Even k such that A307437(k/2) is even. Note that k must be divisible by 4.
%C A341886 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.
%C A341886 Proof: Let m be the smallest number such that k | psi(k).
%C A341886 "<=" If m is odd, then m >= s > t*2^(e+2), but k | psi(t*2^(e+2)), contradicting with minimality of m.
%C A341886 "=>" 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.
%C A341886 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.
%C A341886 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:
%C A341886 (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.
%C A341886 (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.
%C A341886 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.
%C A341886 2^e is a term <=> t*2^e + 1 is composite for t = 1, 2, 3. It follows that this sequence is infinite.
%C A341886 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.
%C A341886 From _Jianing Song_, Feb 27 2021: (Start)
%C A341886 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.
%C A341886 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).
%C A341886 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.
%C A341886 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.
%C A341886 The cases a = 4, 5, 6, 7, 8 are similar. (End)
%H A341886 Chai Wah Wu, <a href="/A341886/b341886.txt">Table of n, a(n) for n = 1..100</a>
%F A341886 a(n) = A341887(n)*2.
%e A341886 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.
%e A341886 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).
%o A341886 (PARI) forstep(n=2, 10000, 2, if(A307437(n)%2==0, print1(2*n, ", "))) \\ see A307437 for its program
%Y A341886 Cf. A002322, A307437, A341887, A007814.
%K A341886 nonn
%O A341886 1,1
%A A341886 _Jianing Song_, Feb 22 2021
%E A341886 More terms from _Chai Wah Wu_, Feb 25 2021