All your base are belong to us

For a mini-puzzle, scroll down to the bottom of this post…

A NEW SEQUENCE FOR THE OEIS!

Inspired by all that 82000 business (see HERE, HERE and HERE), I recently created another sequence centred on the idea of expressing numbers in different bases. My main objective was to get something on to the Online Encyclopaedia of Integer Sequences, which feels like something of a rite of passage for modern day mathematicians. While the 82000 sequence did make it to the OEIS, I was not the person who submitted it and I wanted to actually author one myself.

The sequence that I came up with was very simple:

2, 3, 4, 5, 6, 7, 8, 11, 14, 15, 18, 19, 22, 23, 24, 29, 32, 33, 34, ...

This is the sequence of all positive integers that can be expressed using only the digits 0 and 1 in no more than three different bases. Equivalently, they are the positive integers N, for which there exist at most three integers k > 1 such that N is a sum of distinct non-negative integer powers of k. After a fair amount of backwarding and forwarding, the sequence was accepted into the OEIS as A258946.

All integers N > 3 can trivially be expressed using only the digits 0 and 1 in three different bases:

  • Base 2 : Since 0 and 1 are the only digits used in base 2
  • Base N-1 : As ’11’
  • Base N : As ’10’

The numbers in the sequence cannot be expressed using only 0 and 1 in any other base. I included a table of the first 10000 terms, with the OEIS entry.

OK, so this sequence is not particularly fascinating, but it does suggest several others that could easily be generated for OEIS submission. Most obviously, there is its complement (in the natural numbers), the sequence of all positive integers that can be expressed using only the digits 0 and 1 in at least four different bases. Or you could be more specific and go for those that can be expressed with 0 and 1 in precisely four bases, or precisely five bases, and so on. It may also be interesting to consider only those numbers that are expressible using 0 and 1 in a certain number of bases, where each such expression contains at least two 1s (or at least three 1s, or…), for reasons that I will go into some other time.

Obviously, if you start looking at other digits, there are many other sequences that could be defined. However, while numbers expressible using only 0 and 1 seem somehow mathematically natural, since they are sums of distinct powers of their base, using other digits starts to feel perhaps a little contrived.

In any case, having got my OEIS sequence, I do not intend to do any more, so do feel free to submit any of the above ideas yourself. It would be interesting to see them.

MINI-PUZZLE

In my investigation into the 82000 sequence, I decided that it was likely that 82000 was the only number greater than 1 that was expressible using only 0 and 1 in the four specific bases: 2, 3, 4 and 5.

However, I am certain that there are infinitely many numbers expressible using only 0 and 1 in at least four bases of any kind.

In fact, I am certain that their are infinitely many numbers expressible using only 0 and 1 in at least B bases, for any positive integer B.

How do I know this?

Answers are welcome via the comments.
All comments are moderated, so no chance of giving away the answer.

 

 

2 thoughts on “All your base are belong to us

  1. Troy

    Every positive integer B can be mapped to B-factorial. When written in any base integer b less than B, you will get the integer B!/b followed by a zero. Written in base B!/b, you will get a 1 followed by zeros. And B! has at least B factors for which this is true.

    Reply
    1. thomas Post author

      Not sure I quite understand. This was not what I had in mind, but it looks interesting.

      I’ll work through an example and you can let me know whether it is what you intend:

      Let’s say that your positive integer is 5, so you consider 5!, which is 120. You then suggest writing 120 in a smaller base b. Let’s say b=2 (i.e. binary). Then you say that the answer is 120/2 = 60 followed by a zero. I agree with this, provided that 60 is written in binary also: 120 = ‘1111000’ in base 2, while 60 = ‘111100’.

      Then you suggest writing 120 in base 60, which is ’20’. However, this contains a two, which is no good.

      Have I misunderstood?

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *