cp's OEIS Frontend

A354109 Numbers that are neither an odd prime power nor twice an odd prime power.

%I A354109 #29 Feb 25 2025 13:12:51
%S A354109 1,2,4,8,12,15,16,20,21,24,28,30,32,33,35,36,39,40,42,44,45,48,51,52,
%T A354109 55,56,57,60,63,64,65,66,68,69,70,72,75,76,77,78,80,84,85,87,88,90,91,
%U A354109 92,93,95,96,99,100,102,104,105,108,110,111,112,114,115,116,117,119,120,123,124,126,128,129,130,132,133,135
%N A354109 Numbers that are neither an odd prime power nor twice an odd prime power.
%C A354109 Terms (1, 2, 4) followed by A033949, positive integers that do not have a primitive root.
%C A354109 Also numbers n for which A353768(n) and A353768(A267099(n)) are equal. Proof: if n is an odd prime power or twice such a number, then the odd prime factor in A267099(n) is in the opposite side of 4k+1 / 4k+3 divide of that of the odd prime factor of n, and subtracting one from it will give a number of the form 4k+0 in the other case, and 4k+2 in the other case, and either 4k != 4k+2 (mod 4) when the prime factor is unitary, or then 4k*(4k+1) != (4k+2)*(4k+3) (mod 4), when the odd prime has exponent > 1, so none of such n occur in this sequence. On the other hand, if n has more than two distinct odd prime factors, p and q, then (p-1)(q-1) == 0 (mod 4), or if n is a multiple of 4, then as phi(4) = 2 and phi(2^k) == 0 (mod 4) for k > 2, and with (p-1) giving at least one instance of factor 2, then both A267099(n) and n are guaranteed to be multiples of 4, regardless of whether p (and q) is (are) of the form 4k+1 or 4k+3.
%F A354109 {k | A353768(k) == A354107(k)}.
%t A354109 q[n_] := ! (OddQ[n] && PrimePowerQ[n]) && ! (OddQ[n/2] && PrimePowerQ[n/2]); Select[Range[135], q] (* _Amiram Eldar_, May 20 2022 *)
%o A354109 (PARI)
%o A354109 A354108(n) = (A353768(n) == A353768(A267099(n)));
%o A354109 A354108(n) = ((n && !bitand(n,n-1)) || !isprimepower(n/(2-(n%2))));
%o A354109 isA354109(n) = A354108(n);
%o A354109 (Python)
%o A354109 from sympy import primepi, integer_nthroot
%o A354109 def A354109(n):
%o A354109     def f(x): return int(n+sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length()))+sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
%o A354109     m, k = n, f(n)
%o A354109     while m != k: m, k = k, f(k)
%o A354109     return m # _Chai Wah Wu_, Feb 25 2025
%Y A354109 Cf. A033949, A353768, A267099, A354107, A354108 (characteristic function), A354189 (subsequence).
%K A354109 nonn
%O A354109 1,2
%A A354109 _Antti Karttunen_, May 18 2022