A342172 a(n) is the smallest n-bit number having the most common prime signature among n-bit numbers. (In case more than one prime signature is tied for most common, choose the smallest n-bit number whose prime signature is one of those tied.)

1, 2, 5, 10, 17, 33, 65, 129, 259, 514, 1027, 2049, 4097, 8193, 16387, 32773, 65542, 131073, 262149, 524291, 1048578, 2097154, 4194305, 8388611, 16777217, 33554437, 67108870, 134217734, 268435462, 536870913, 1073741829, 2147483651, 4294967298, 8589934594

Offset

1,2

Comments

Let S be the prime signature that occurs most frequently among the numbers in the interval I_n = [2^(n-1), 2^n - 1]; then a(n) is the smallest number in I_n whose prime signature is S.

For each n in 1..34, there is only one prime signature in I_n that occurs with the maximum frequency.

Conjecture: for all n >= 1, there is only one prime signature in I_n that occurs with the maximum frequency.

For each n in 1..34, the most common prime signature in I_n is squarefree: 1 for n=1, p for n=2,3,5; p*q for n=4,6..19; p*q*r for 20..34. From limited sampling of portions of the interval I_n for a number of values of n > 34, it appears that p*q*r continues to be the most common prime signature among n-bit numbers for values of n up to roughly 60; for values larger than about 60, p*q*r*s becomes more common than p*q*r.

Is the most common prime signature in I_n squarefree for every n?

Links

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

Example

For n=1, the interval I_1 consists only of the single integer 1, so a(1)=1. (We can disregard 0 even though it is a 1-bit number because 0 has no prime signature.)
For n=2, the integers in I_2 = [2, 3] have the same prime signature (both are primes), so a(2)=1.
For n=3, the integers in I_3 = [4, 7] are 4=2^2, 5 (prime), 6=2*3, and 7 (prime), so their prime signatures are p^2, p, p*q, and p, respectively, where p and q are distinct primes; the prime signature that occurs most frequently is p, which is occurs at 5 and 7, so a(3)=5.
For n=4, I_4 = [8, 15]; the integers are 8=2^3, 9=3^2, 10=2*5, 11 (prime), 12=2^2*3, 13 (prime), 14=2*7, and 15=3*5, so the prime signatures are p^3, p^2, p*q, p, p^2*q, p, p*q, and p*q, of which p*q occurs most frequently (at 10, 14, and 15), so a(4)=10.
For n=20, of the 524288 integers in the interval [524288, 1048575], 109245 (about 21%) have the prime signature p*q*r; this is the most common prime signature in the interval, and the smallest number having that prime signature in the interval is 524291 = 29*101*179, so a(20)=524291.

Prog

(Python)
from sympy import factorint
from collections import Counter
def a(n):
  c, d = Counter(), dict()
  for i in range(2**(n-1), 2**n):
    t = tuple(sorted(factorint(i).values()))
    if t not in d: d[t] = i
    c.update([t])
  return d[c.most_common(1)[0][0]]
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Mar 27 2021

Crossrefs

Cf. A046523.

Sequence in context: A038358 A107482 A227363 * A262406 A308600 A308604

Adjacent sequences: A342169 A342170 A342171 * A342173 A342174 A342175

Keyword

nonn

Author

Jon E. Schoenfield, Mar 26 2021

Extensions

a(26)-a(29) from Jinyuan Wang, Mar 27 2021

a(30)-a(34) from Jon E. Schoenfield, Mar 28 2021

Status

approved