Friday, January 28, 2022

Prime Number - prefixes

As part of a personal project regarding prime numbers, I created a toolkit to help do some research and one of the interesting finds was related to prime prefixes.

First let me define prime numbers for my use; A prime number is an integer greater than or equal to 1 which can ONLY be expressed by multiplication as itself times 1.  Some definitions seem to exclude 1 but I include it. So the first 5 prime numbers are 1, 2, 3, 5, 7.

As for prefixes, let me first describe a process for constructing prime numbers of 3 or greater.

Each prime number (Pn) > 3 can be created from the sum of some unique subset of the primes P1 to Pn-2  which are added to Pn-1 . Where n is an integer > 0.  If you list out primes in vertical list, n represents the row number of the prime.  P1 represents the prime 1.  P2 represents the prime 2.  P5 represents the prime 7.

Examples:

P1 = 1

P2 = 2

P3 is 3  =>    P1 + P(3-1)    =>    1 + P2     =>  1 + 2    =>  1 + 2 => 3

P4 is 5  =>    P2 + P(4-1)    =>    2 + P3    =>  2 + 3    =>  5 

P5 is 7  =>    P2 + P(5-1)    =>    2 + P =>  2 + 5    =>  7

P6 is 11 =>    P1 + P3 + P(6-1) => 1 + 3 + P5 =>    1 + 3 + 7 =>  11

So "prefix" represents the subset of primes in the range P1 to Pn-2 that are added to Pn-1 to get the value Pn.

So:

P3 has a prefix of a single prime which is 1.

P4  has a prefix of a single prime which is 2.

P5 has a prefix of a single prime which is 2.

P6 has a prefix of two primes: 1,3.

Given those definitions and general method; I added some support to my Prime Tool Kit to find the prefixes for the first 5,000,000 primes. It turned out that only 98 prefixes were needed for that 5,000,000 prime numbers.

Below are the prefixes and the counts of primes associated with each prefix.  Note that the empty prefix [] was for Primes 1 and 2 and the Prefix of [1] is from prime 3. One odd observation is that I didn't run across a prefix consisting of just [1,3,5] - this may be due to some primes having multiple possible prefixes and my algorithm only selects one. One other interesting display form of this would be a tree form (so counts would apply to any common prefix among the prefixes) and show the sum from the current node either down or up the tree.

Prefix: []  count: [2]

Prefix: [1]  count: [1]

Prefix: [2]  count: [385375]

Prefix: [1,3]  count: [385268]

Prefix: [1,2,3]  count: [672224]

Prefix: [1,2,5]  count: [292025]

Prefix: [2,5,7]  count: [255156]

Prefix: [2,3,5]  count: [375266]

Prefix: [2,3,7]  count: [469249]

Prefix: [1,2,3,5,7]  count: [333879]

Prefix: [1,3,5,11]  count: [175644]

Prefix: [1,2,3,5,11]  count: [152378]

Prefix: [2,3,5,11,13]  count: [61166]

Prefix: [1,2,3,7,11]  count: [222949]

Prefix: [1,3,5,7]  count: [187797]

Prefix: [1,2,5,7,11]  count: [103143]

Prefix: [2,3,5,7,11]  count: [111693]

Prefix: [2,3,5,7,13]  count: [191643]

Prefix: [1,2,5,11,13]  count: [58527]

Prefix: [2,3,7,11,13]  count: [97522]

Prefix: [1,3,5,7,11,17]  count: [29594]

Prefix: [1,2,3,5,7,11,13]  count: [73926]

Prefix: [1,3,5,7,11,13]  count: [51884]

Prefix: [1,2,3,5,11,13,17]  count: [17392]

Prefix: [1,2,3,5,7,13,17]  count: [42347]

Prefix: [2,5,7,11,13]  count: [44256]

Prefix: [2,3,7,11,13,17,19]  count: [7043]

Prefix: [1,3,5,11,13,17]  count: [23387]

Prefix: [1,2,5,7,11,17,19]  count: [7155]

Prefix: [1,2,3,7,11,13,17]  count: [28388]

Prefix: [2,3,5,7,11,13,19]  count: [23918]

Prefix: [2,3,5,7,11,13,17]  count: [12368]

Prefix: [1,2,3,5,7,11,17]  count: [25017]

Prefix: [1,2,5,7,11,13,17]  count: [13978]

Prefix: [2,3,5,7,11,17,19]  count: [7398]

Prefix: [1,2,5,11,13,17,19]  count: [5183]

Prefix: [1,3,5,7,11,17,19,23]  count: [1320]

Prefix: [2,3,5,7,13,17,19]  count: [12986]

Prefix: [2,3,5,11,13,17,19]  count: [7383]

Prefix: [1,2,3,5,7,11,13,17,19]  count: [5638]

Prefix: [1,3,5,7,11,13,17,19]  count: [2950]

Prefix: [1,2,3,5,7,11,13,17,23]  count: [1952]

Prefix: [1,2,3,7,11,13,17,19,23]  count: [1325]

Prefix: [2,3,5,7,11,13,19,23,29]  count: [260]

Prefix: [2,3,5,7,11,13,17,19,23]  count: [725]

Prefix: [2,5,7,11,13,17,19]  count: [3586]

Prefix: [1,2,3,5,7,13,17,19,23]  count: [2750]

Prefix: [1,2,3,5,7,11,13,19,23]  count: [3882]

Prefix: [1,2,5,7,11,17,19,23,29]  count: [389]

Prefix: [1,3,5,7,11,13,17,23]  count: [2723]

Prefix: [1,2,3,5,7,11,17,19,23]  count: [1370]

Prefix: [1,2,5,7,11,13,17,19,23]  count: [689]

Prefix: [1,3,5,11,13,17,19,23]  count: [881]

Prefix: [2,3,5,7,11,13,17,19,29]  count: [338]

Prefix: [1,2,3,5,11,13,17,19,23]  count: [800]

Prefix: [2,3,5,7,13,17,19,23,29]  count: [151]

Prefix: [1,2,3,5,7,11,13,17,19,23,31]  count: [105]

Prefix: [1,2,5,7,11,13,17,19,29]  count: [396]

Prefix: [1,2,3,7,11,13,17,19,29]  count: [857]

Prefix: [2,3,5,7,11,13,17,23,29]  count: [377]

Prefix: [2,5,7,11,13,17,19,23,29]  count: [163]

Prefix: [1,2,5,11,13,17,19,23,29]  count: [353]

Prefix: [1,2,3,5,7,11,17,19,23,29,31]  count: [30]

Prefix: [1,2,5,7,11,13,17,23,29]  count: [597]

Prefix: [2,3,5,11,13,17,19,23,29]  count: [107]

Prefix: [1,2,3,5,7,11,13,17,19,29,31]  count: [70]

Prefix: [1,3,5,7,11,13,17,19,23,29]  count: [58]

Prefix: [1,2,3,5,11,13,17,19,23,29,31]  count: [8]

Prefix: [1,2,3,5,7,11,13,17,19,23,29]  count: [58]

Prefix: [2,3,5,7,11,17,19,23,29]  count: [151]

Prefix: [1,3,5,7,11,17,19,23,29,31]  count: [18]

Prefix: [1,3,5,7,11,13,17,19,29,31]  count: [34]

Prefix: [2,3,7,11,13,17,19,23,29]  count: [115]

Prefix: [2,5,7,11,13,17,19,29,31]  count: [36]

Prefix: [1,3,5,7,11,13,17,23,29,31]  count: [44]

Prefix: [1,3,5,11,13,17,19,23,29,31]  count: [18]

Prefix: [1,2,3,5,7,11,13,17,23,29,31]  count: [27]

Prefix: [1,2,3,5,7,11,13,19,23,29,31]  count: [37]

Prefix: [1,2,3,5,7,13,17,19,23,29,31]  count: [29]

Prefix: [2,3,5,7,11,13,19,23,29,31,37]  count: [1]

Prefix: [1,2,3,7,11,13,17,19,23,29,31]  count: [18]

Prefix: [1,2,5,7,11,13,17,19,23,29,37]  count: [4]

Prefix: [1,2,3,5,7,11,13,17,19,23,31,37,41]  count: [1]

Prefix: [1,2,3,7,11,13,17,19,29,31,37]  count: [4]

Prefix: [2,3,5,7,11,13,17,19,23,29,31]  count: [8]

Prefix: [1,2,5,7,11,17,19,23,29,31,37]  count: [1]

Prefix: [2,3,5,7,11,13,17,19,23,31,37]  count: [7]

Prefix: [1,2,5,7,11,13,17,23,29,31,37]  count: [4]

Prefix: [1,2,5,7,11,13,17,19,29,31,37]  count: [1]

Prefix: [1,2,3,7,11,13,17,19,23,29,37]  count: [6]

Prefix: [2,3,5,7,11,13,17,23,29,31,37]  count: [4]

Prefix: [1,2,3,5,7,11,13,17,19,23,29,31,37]  count: [1]

Prefix: [1,2,3,5,7,11,13,17,23,29,31,37,41]  count: [1]

Prefix: [1,2,5,7,11,13,17,19,23,29,31]  count: [7]

Prefix: [2,3,5,7,11,13,17,19,29,31,37]  count: [3]

Prefix: [1,3,5,7,11,13,17,19,23,29,31,37]  count: [1]

Prefix: [2,3,5,7,11,17,19,23,29,31,37]  count: [1]

Prefix: [2,3,5,7,11,13,17,19,23,29,37]  count: [1]

Total handled = 5000001


Thanks for reading!

Scott

No comments:

Post a Comment