The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.) 0
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 (list; graph; refs; listen; history; text; internal format)



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?


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


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.



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


  return d[c.most_common(1)[0][0]]

print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Mar 27 2021


Cf. A046523.

Sequence in context: A038358 A107482 A227363 * A262406 A308600 A308604

Adjacent sequences:  A342169 A342170 A342171 * A342173 A342174 A342175




Jon E. Schoenfield, Mar 26 2021


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

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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 15:38 EDT 2021. Contains 345085 sequences. (Running on oeis4.)