Building Block Numbers

The prime numbers are considered the building blocks of the positive integers because every composite number can be expressed as a product of prime numbers. However, the OEIS A086424 offers an alternative set of building blocks:

A086424 Numbers needed to generate all other natural numbers, only allowing multiplication and addition. Each number can be used only once.

These numbers are: 

1, 2, 4, 11, 25, 64, 171, 569, 3406, 27697, 243374, 1759619, 28381401, 222323189, 3416307938, 26838745347

Here is an extract from the OEIS comments:

• 10 is not in the sequence because (4+1)*2 = 10.
• 11 is in the sequence because there is no way to get 11 by using the earlier terms.
• 509 is not in the sequence because
  509 = (1+25)*(2+11)+171.

The number associated with my diurnal age today is 27697 and this is the first number that cannot be expressed in terms of the numbers 1, 2, 4, 11, 25, 64, 171, 569 and 3406 using only multiplication or addition and using each number only once. From now on, up to but not including 243374, every number can be expressed in terms of 1, 2, 4, 11, 25, 64, 171, 569, 3406 and 27697. This is a big deal.

GEMINI WAS ABLE TO CHANGE PARI CODE
TO PYTHON AFTER A FEW TRIES

The OEIS comments offer some PARI code to generate this list of numbers and, after many errors on the part of Gemini, I was able to get to produce some working PYTHON code that will do the same job, albeit slowly. Here is the code:

from sage.all import *

def Ww(v):

    """

    Calculates the Ww function for a given list of integers.

    Args:

        v: A list of integers.

    Returns:

        A list of integers resulting from the Ww function.

    """

    if len(v) == 2:

        return [v[0], v[1], v[0] + v[1], v[0] * v[1]]

    else:

        V = []

        for i in range(len(v)):

            for j in range(i + 1, len(v)):

                t = v[:i] + v[i+1:j] + v[j+1:]

                if t:

                    V.extend(Ww(t + [v[i] + v[j]]))

                    V.extend(Ww(t + [v[i] * v[j]]))

        return sorted(set(V))  # Remove duplicates

a = [Integer(1), Integer(2), Integer(4)]

for n in range(3, 10):

    V = Ww(a)

    for i in range(2 * a[-1], len(V) + 1):

        if V[i - 1] > i:

            a.append(i)

            print(f"a = {a}")

            break

    else:

        print(f"No solution found for n = {n}")  

 

EVERY NUMBER UP TO BUT NOT INCLUDING 27697

CAN BE EXPRESSED IN TERMS OF

1, 2, 4, 11, 25, 64, 171, 569 and 3406

USING ONLY ADDITION AND MULTIPLICATION

AND USING ONE NUMBER ONLY ONCE

Of course the execution of this code on SageMathCell will quickly time out and it will only generate the numbers up to 171. However, running it in a Jupyter notebook on an M1 Macbook Air, it will generate the numbers up to 3406 fairly quickly but after an hour or so it never got to 27697 so I stopped it. 

I asked Gemini to come up with an algorithm in Python to express a given number in terms of these new "building blocks" but it consistently failed so I gave up. However, it will be easy initially for numbers greater than 27697. For example:

• 27698 = 27697 + 1
• 27699 = 27697 + 2
• 27700 = 27697 + 2 + 1
• 27701 = 27697 + 4 etc.

I'll continue to do this as an exercise associated with my daily number analysis. Figure 1 shows an analysis of the building block numbers and their factors. It can be seen that the only prime numbers are 2, 11, 569 and 27697. It should be noted that the property these numbers have collectively is NOT base dependent.

Figure 1

These particular building blocks are remarkably economical considering how many unique primes we would require to "build" all the numbers from 2 to 27697. It is in fact 3020. These blocks only require nine blocks: 1, 2, 4, 11, 25, 64, 171, 569 and 3406. They become even more economical for larger numbers. For example in the range up to 243373 (one less than 243374), we require 21494 unique primes but only ten of our new building blocks: 1, 2, 4, 11, 25, 64, 171, 569, 3406 and 27697. However, unlike the prime building blocks, representations using these new building blocks are not unique. For example, 12 can be represented as 11 + 1 or (1 + 2) * 4. Remember, bracketing is allowed.