A339870 - OEIS

%I #32 Feb 18 2021 00:50:09

%S 85,561,1105,1261,1285,2465,4369,6601,8245,8481,9061,9605,10585,16405,

%T 16705,17733,18721,19669,21845,23001,28645,30889,38165,42121,43165,

%U 46657,54741,56797,57205,62745,65365,74593,78013,83665,88561,91001,106141,117181,124645,126701,134521,136981,141661,162401,171205,176437

%N Composite numbers k of the form 4u+1 for which the odd part of phi(k) divides k-1.

%C From _Antti Karttunen_, Dec 26 2020: (Start)

%C Equally, squarefree composite numbers k of the form 4u+1 for which A336466(k) divides k-1. This follows because on squarefree n, A336466(n) = A053575(n).

%C No common terms with A016105, because 4xy + 2(x+y) + 1 does not divide 4xy + 3(x+y) + 2 for any distinct x, y >= 0 (where 4x+3 and 4y+3 are the two prime factors of Blum integers).

%C This can also seen by another way: If this sequence contained any Blum integers, then, because A016105 is a subsequence of A339817, we would have found a composite number n satisfying Lehmer's totient problem y * phi(n) = n-1, for some integer y > 1. But Lehmer proved that such solutions should have at least 7 distinct prime factors, while Blum integers have only two.

%C Moreover, it seems that none of the terms of A167181 may occur here, and a few of A137409 (i.e., of A125667). See A339875 for those terms.

%C (End)

%H Antti Karttunen, <a href="/A339870/b339870.txt">Table of n, a(n) for n = 1..1316</a>

%H D. H. Lehmer, <a href="http://dx.doi.org/10.1090/s0002-9904-1932-05521-5">On Euler's totient function</a>, Bulletin of the American Mathematical Society, 38 (1932), 745-751.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lehmer&#39;s_totient_problem">Lehmer's totient problem</a>

%e 85 = 4*21 + 1 = 5*17, thus phi(85) = 4*16 = 64, the odd part of which is A000265(64) = 1, which certainly divides 85-1, therefore 85 is included as a term.

%e 561 = 4*140 + 1 = 3*11*17, thus phi(561) = 2*10*16 = 320, the odd part of which is A000265(320) = 5, which divides 560, therefore 561 is included.

%t odd[n_] := n/2^IntegerExponent[n, 2]; Select[4*Range[45000] + 1, CompositeQ[#] && Divisible[# - 1, odd[EulerPhi[#]]] &] (* _Amiram Eldar_, Feb 17 2021 *)

%o (PARI)

%o A000265(n) = (n>>valuation(n, 2));

%o isA339870(n) = ((n>1)&&!isprime(n)&&(1==(n%4))&&!((n-1)%A000265(eulerphi(n))));

%Y Cf. A000010, A000265, A016105, A053575, A137409, A167181, A336466.

%Y Subsequence of A005117.

%Y Intersection of A091113 and A339880.

%Y Cf. A339875 (a subsequence).

%Y Cf. also comments in A339817.

%K nonn

%O 1,1

%A _Antti Karttunen_, Dec 22 2020