5
$\begingroup$

One day, I wanted to be able to represent all numbers less than 20 without erasers or computers (Don't ask, OK?) I immediately thought of making cards1. For example, in base 10, you need 2 for the tens digit (saying 1,2), when there is no tens digit, don't put a card) and 10 for the ones digits, saying 1-9. However, that's a lot of cards! The smallest number of cards needed is 8, for base 3.

1 The cards are one sided, so no flipping cards around

In fact, most numbers have base 3 as the least amount of cards needed. Can you find the smallest 5 numbers, excluding the trivial examples 1 and 3 where "number" is like the 20 in the example (note 20 is not an answer)that has a base other than 3 that requires less cards?

A formula for cards needed in base b and numbers up to n is:

(First digit of n in base b)+(b*length of n in base b)-b.

No computers.

To clarify, no rearranging cards. Tens digits cards can't go to the ones digits, for example.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This is closely related to radix economy. $\endgroup$
    – f''
    Jul 7, 2016 at 15:19
  • $\begingroup$ @f'' hmm I never saw that $\endgroup$
    – user17008
    Jul 7, 2016 at 15:20
  • 4
    $\begingroup$ I'm finding the wording of this puzzle a little hard to follow. It sounds like an interesting puzzle, but ... it needs some cleanup. $\endgroup$
    – Ian MacDonald
    Jul 7, 2016 at 15:25

2 Answers 2

Reset to default
6
$\begingroup$

My immediate first thought is look for numbers one larger than a power of 3 in order to "capture" and instance where the number of cards had to go up by one in base 3.
The first example would be 4 (3+1), which requires 4 cards in base 3, and 5 in base 2 and 5 in base 4. Tragic lack of efficiency, in fact base 1 ties it with 4. So 4 failed.
The next case would be 10 (9+1). In this case if we check base 3 the number to beat is 7. 10 base 3 is 101. Which is 7 cards. A quick peek at base 4 reveals 22 which only requires 6 cards. So 10 works. 11 Also will work as this is 23 in base 4 still only needing six cards. Alas 12 would be 30 bringing it up to 7 cards.

So, so far 10 and 11. Now comes the question, did we miss any below. As base 3 wins at 4, we know it wins 5. But at 6 does anyone pass it. 3=>5 (20) 4=>5 (12) 2=>5 (110). Tragically no. (Also it is trivial to show base 5 doesn't work as it is greater than 5 so will use at least 5 [in this case 6]). Having supremacy at 6 will maintain control until 8. Does it get passed at 9? --at this very moment I realize the number of cards goes up at powers of 3 not one above powers of three and I am very optimistic about 9.

  1. Base 3=>7 (100), Base 4=>6 (21).

So right now 9, 10 ,11.

Now lets check at 18 where it goes to 200 or 8 cards. 2=>9 (10010), 4=>9 (102). 5=>8 (31). 6=>8 (24). Looks like no one is taking the crown at 18. At this point I realize going up on a power of 3 adds 2 cards rather than just 1 because you have the 0 digit added to the second largest spot and the leading 1.

27! 3=>10 1000. 2=>11 (110011). 4=>9! (123) so 27 works

28 3=>10 1001. 4=>9 (130) so 28 rounds out our top 5.

9 10 11 27 28

Summary of my Theory once I ran into some trial and error: Upon increasing number of digits necessary (10, 100, 1000 / 3, 9, 27) you suddenly add 2 more cards (the leading digit and 0 in the second digit) this gives other bases a brief chance to catch up to our power house Base3.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Deep apologies for the overall flow of the post that was the discovery process not quite the proof that would be submitted to a journal but it is a pretty accurate account of what I was thinking as I went about attempting to solve it. It strikes me as possible I missed some, but I somewhat think I may have done it right. $\endgroup$
    – Going hamateur
    Jul 7, 2016 at 15:45
  • $\begingroup$ Good job! You got it. $\endgroup$
    – user17008
    Jul 7, 2016 at 16:11
  • $\begingroup$ Thanks for the cool question, I enjoyed it. I find it interesting that 3 usually wins. Is that true even/especially with larger numbers? Curious why that would be, I sort of imagine it has something to do with the number e, because that is just what math seems to like doing and then the anomalies probably would occur due to discretization or something... $\endgroup$
    – Going hamateur
    Jul 7, 2016 at 16:16
  • $\begingroup$ It might not be related to e, because then usually base 2 would come up when base 3 doesn't.. Or I'm just really bad at math. $\endgroup$
    – user17008
    Jul 7, 2016 at 16:24
  • $\begingroup$ See I see why you could think that but my reasoning is related to logs, which would be much more relevant in base system as you are sort of raising stuff to powers: log 2 = .301 log e = .434 log 3 = .477 log 4 = .602. Though: .434 is farther from .602 (4) than .301 (2). So you still win. Hmmm... well its a curiousity. I still suspect the muckery of e. Though who knows it could be pi (log pi = .497) $\endgroup$
    – Going hamateur
    Jul 7, 2016 at 16:33
2
$\begingroup$

NOTE: Not an answer. Going hamateur has posted the solution to the problem given.

As an interesting observation* sometimes the (mixed radix) primorial number system will perform better than the best integer base.

An example is $n=81$ where bases $2,3,4,5$ all use $13$ cards and higher bases use more. Here the primorial base uses only $12$ cards -
$\{1,2\},\{0,1,2,3,4\},\{0,1,2\},\{0,1\}$
for the place values $30,6,2,1$ respectively:

 1:    1   |   18:  300   |   35: 1021   |   52: 1320   |   69: 2111
 2:   10   |   19:  301   |   36: 1100   |   53: 1321   |   70: 2120
 3:   11   |   20:  310   |   37: 1101   |   54: 1400   |   71: 2121
 4:   20   |   21:  311   |   38: 1110   |   55: 1401   |   72: 2200
 5:   21   |   22:  320   |   39: 1111   |   56: 1410   |   73: 2201
 6:  100   |   23:  321   |   40: 1120   |   57: 1411   |   74: 2210
 7:  101   |   24:  400   |   41: 1121   |   58: 1420   |   75: 2211
 8:  110   |   25:  401   |   42: 1200   |   59: 1421   |   76: 2220
 9:  111   |   26:  410   |   43: 1201   |   60: 2000   |   77: 2221
10:  120   |   27:  411   |   44: 1210   |   61: 2001   |   78: 2300
11:  121   |   28:  420   |   45: 1211   |   62: 2010   |   79: 2301
12:  200   |   29:  421   |   46: 1220   |   63: 2011   |   80: 2310
13:  201   |   30: 1000   |   47: 1221   |   64: 2020   |   81: 2311
14:  210   |   31: 1001   |   48: 1300   |   65: 2021
15:  211   |   32: 1010   |   49: 1301   |   66: 2100
16:  220   |   33: 1011   |   50: 1310   |   67: 2101
17:  221   |   34: 1020   |   51: 1311   |   68: 2110

Furthermore $13$ cards are not required until $n>89$, so it wins in those cases too.
It might be that these $9$ cases are the only ones where the primorial beats the best integer base.
At the $n=3^5$ mark ($243\leq n\leq255$) base $4$ wins with $16$ cards over the primorial's $18$.

* Sorry, but I did end up resorting to using a computer for this, but thought it worth posting anyway.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Definitely an interesting enough extension of the problem to merit computer usage, thanks for sharing. $\endgroup$
    – Going hamateur
    Jul 8, 2016 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.