Showing posts with label number system. Show all posts
Showing posts with label number system. Show all posts

Friday, 6 June 2025

Binomial Number System

I made a post titled Encoding Secret Numbers only recently on the 8th of May 2025 in which I looked at how the Heinz number and Gray Code could be used to encrypt a number. An article I read today suggested another encryption method that is more arcane than the two previously mentioned. The article states that every non-negative integer n can be written as:$$ \binom{a}{1} + \binom{b}{2} + \binom{c}{3} \text{ where } a \leq b < c $$The article goes on to say that:

You can find \(a\), \(b\) and \(c\) much as you would find the representation in many other number systems: first find the largest possible \(c\), then the largest possible \(b \) for what’s left, and then the remainder is \(a\). 
In order to find \(c\), we start with the observation that the binomial coefficient C(\(k\), 3) is less than \(k^3\)/6 and so \(c\) is less than the cube root of \(6n\). We can use this as an initial lower bound on \(c\) then search incrementally. If we wanted to be more efficient, we could do some sort of binary search.

Figure 1 shows the Python code to find \(a\), \(b\) and \(c\):


Figure 1: permalink

In the article the term \( \textbf{binomial number system} \) is used to describe this approach. Applying the code to the number associated with my diurnal age today (27823) we find that \(a=12\), \(b=14\) and \(c=56\) so that:$$27823= \binom{12}{1} + \binom{14}{2} + \binom{56}{3} $$This encrypted version of 27823 could be represented as 12. 14. 56 with the dots being added to prevent possible ambiguity although commas or dashes or whatever could be used as well. The encrypted number has the same number of digits as the number being encrypted.

Unless someone knew about this "binomial number system" it would be impossible to guess what number was being encrypted. Once the binomial "key" is applied however, we find that:$$12. \,14. \, \,56 \rightarrow 12 + 91 + 27720 = 27823$$What about the number 1? Well, in that case, we \(a=b=0\) and \(c=3\) because:$$1=\binom{0}{1}+\binom{0}{2}+\binom{3}{3} \rightarrow 0. \, 0. \, 3$$What about the number 2. In this case we have \(a=0\), \(b=2\) and \(c=3\) so that:$$2=\binom{0}{1}+\binom{2}{2}+\binom{3}{3} \rightarrow 0. \, 2. \, 3$$Of course for the number 3 we have \(a=1\), \(b=2\) and \(c=3\) so that:$$3=\binom{1}{1}+\binom{2}{2}+\binom{3}{3} \rightarrow 1. \, 2. \, 3$$Interestingly, the final comment that the author of the referenced article makes is that "you could use any number of binomial terms, not just three". One binomial term C(\(a\), 1) just corresponds to the positive integers since:$$ \binom{a}{1}=a$$Two binomial terms work as well of course. For example:$$\binom{2}{1}+\binom{5}{2}=2+10 =12$$Notice that this representation of 12 (and any other number) is unique because even though:$$ \binom{6}{1}+\binom{4}{3}=6 + 6=12$$this representation contravenes the rule that \(a \leq b\) since \(a=6\) and \(b=4\). All very interesting.

Sunday, 14 February 2021

Primorial Number System

 I've written about the factorial number system in two previous posts:

It is a mixed radix number system and so is the primorial number system that uses the primorials (progressive products of primes):
  • 2
  • 2 x 3 = 6
  • 2 x 3 x 5 = 30
  • 2 x 3 x 5 x 7 = 210
  • 2 x 3 x 5 x 7 x 11 = 2310
  • 2 x 3 x 5 x 7 x 11 x 13 = 30030
  • 2 x 3 x 5 x 7 x 11 x 13 x 17 = 510510
  • 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 = 9699690 etc.
It's easy enough to set up an algorithm in SageMath that will convert decimal number to primorial digits. In decreasing order, the primorials below ten million are 9699690, 510510, 30030, 2310, 210, 30, 6 and 2. These numbers can serve as bases to represent any number up to 10,242,789 (which has representation as 111111111). Here is the algorithm (permalink) that will return the primorial base representation of any number up to 10,242,789. The example returns the representation for numbers the numbers 27717 and 27718 (where we don't need  any primorials above those numbers):

P=[2310,210,30,6,2]
for number in [27717..27718]:
    original=number
    N=[]
    for p in P:
        N.append(number//p)
        number=number%p
    if is_odd(original):
        N.append(1)
    else:
        N.append(0)
    primorial=""
    for n in N:
        primorial+=str(n)+" "
    print(original,"-->",primorial)

27717 --> 11 10 6 4 1 1 
27718 --> 11 10 6 4 2 0 

Notice the spaces between the base-10 numbers in the primorial base representation (although colons are more commonly used) where:

27717 = 11 x 2310 + 10 x 210 + 6 x 30 + 4 x 6+ 1 x 2 + 1
27718 = 11 x 2310 + 10 x 210 + 6 x 30 + 4 x 6 + 1 x 2 + 0

For more information see this source. For any number in the range up to 40000 that I focus on, the letter A can be used for 10 and the letter B for 11 can be used. Additional letters can be used for larger numbers (up to a point). The colons, spaces or other separators are then not needed and the resultant single digits can be concatenated without ambiguity. Thus:$$27717_{10} \rightarrow BA6411_{primorial}\\27718_{10} \rightarrow BA6420_{primorial}$$However, it needs to be remembered that the numbers on the right (directly above) are not base 12 numbers and that the digits are merely convenient placeholders. To emphasise this, consider the base 12 equivalents of 27717 and 27718:$$27717_{10} \rightarrow 14059_{12}\\27718_{10} \rightarrow 1405A_{12}$$So what stimulated my interest in primorial number systems? Well, like most of my posts, it was prompted by my analysis of the number representing my diurnal age. Today I turned 26250 days old and this number has a striking factorisation:$$26250=7 \times 5^4 \times 3 \times  2$$The first entry for this number in the OEIS is A276086:


   A276086

Prime product form of primorial base expansion of \(n\): digits in primorial base  representation of \(n\) become the exponents of successive prime factors whose product a(\(n\)) is.  


It took me some time to understand what this meant. In the case of 26250, \(n\)=57 and its primorial base expansion is 1411. The resulting digits because the exponents of successive prime factors that multiply together to give 26250. In other words:$$7^1 \times 5^4 \times 3^1 \times 2^1 = 26250$$