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

1, 2, 4, 8, 12, 15, 16, 20, 21, 24, 28, 30, 32, 33, 35, 36, 39, 40, 42, 44, 45, 48, 51, 52, 55, 56, 57, 60, 63, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 84, 85, 87, 88, 90, 91, 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

Offset: 1

Author

Antti Karttunen, May 18 2022

Keywords

• nonn

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.

Crossrefs

Cf. A033949, A353768, A267099, A354107, A354108 (characteristic function), A354189 (subsequence).

Programs

Mathematica

q[n_] := ! (OddQ[n] && PrimePowerQ[n]) && ! (OddQ[n/2] && PrimePowerQ[n/2]); Select[Range[135], q] (* Amiram Eldar, May 20 2022 *)

PARI

A354108(n) = (A353768(n) == A353768(A267099(n)));
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

Formula

{k | A353768(k) == A354107(k)}.