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,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.

Links

Table of n, a(n) for n=1..75.

Formula

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

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) = (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

Crossrefs

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

Sequence in context: A328838 A064711 A050865 * A354919 A288514 A350616

Adjacent sequences: A354106 A354107 A354108 * A354110 A354111 A354112

Keyword

nonn,changed

Author

Antti Karttunen, May 18 2022

Status

approved