OFFSET
1,2
COMMENTS
Terms (1, 2, 4) followed by A033949, positive integers that do not have a primitive root.
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.
MATHEMATICA
q[n_] := ! (OddQ[n] && PrimePowerQ[n]) && ! (OddQ[n/2] && PrimePowerQ[n/2]); Select[Range[135], q] (* Amiram Eldar, May 20 2022 *)
PROG
(PARI)
A354108(n) = ((n && !bitand(n, n-1)) || !isprimepower(n/(2-(n%2))));
isA354109(n) = A354108(n);
(Python)
from sympy import primepi, integer_nthroot
def A354109(n):
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)))
m, k = n, f(n)
while m != k: m, k = k, f(k)
return m # Chai Wah Wu, Feb 25 2025
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Antti Karttunen, May 18 2022
STATUS
approved