in reply to Can It Be Written In Base X With Only 1s And 0s

There is a pattern, but it is quite hard to describe. It's a -- for want of a better term -- a reducing, recursive power series.

So, for base 3, these are all the numbers that only use 0 or 1:

   |                                                                  
+                                         +3^4
   |                                                      +3^3        
+                                      |                              
+          +3^3
   |                         |  +3^2                    |             
+            +3^2                      |                     +3^2     
+            |                  +3^2
   |             +3^1        |               +3^1       |             
+ +3^1         |          +3^1         |           +3^1        |      
++3^1        |        +3^1        |        +3^1
   |      +3^0    |    +3^0  |        +3^0    |   +3^0  |        +3^0 
+  |   +3^0    |    +3^0   |   +3^0    |       +3^0  |   +3^0  |  +3^0
+  |  +3^0   |   +3^0   |  +3^0   |  +3^0   |  +3^0 
---+--------------+----------+----------------+---------+-------------
+--+-----------+-----------+-----------+-------------+---------+------
+--+---------+----------+---------+---------+------
^0 |   1                     |                          |             
+                                      | 
^1 |   3     4               |                          |             
+                                      | 
^2 |   9    10     12    13  |                          |             
+                                      | 
^3 |  27    28     30    31  |    36    37    39    40  |             
+                                      | 
^4 |  81    82     84    85  |    90    91    93    94  |   108   109 
+  111   112   117   118   120   121   | 
^5 | 243   244    246   247  |   252   253   255   256  |   270   271 
+  273   274   279   280   282   283   |  324  325  327  328  333  334
+  336  337  351  352  354  355  360  361  363  364
^6 | 729   ...

[download]

The +3^0s (ie.+1) is always applied to the number immediately to its left to derive the number underneath it.

The +3^1s (ie.+3) is always applied to the number two to its left to derive the number underneath it.

The +3^2s (ie.+9) is always applied to the number four to its left to derive the number underneath it. Etc.

Clear as mud right! Can't think of a better way to describe it.

For base-4, the same pattern emerges:

                                                                      
+                         +4^4
                                                    +4^3              
+                                                                 +4^3
                             +4^2                                     
+  +4^2                                       +4^2                    
+                +4^2
                +4^1                   +4^1                   +4^1    
+            +4^1                   +4^1                +4^1          
+      +4^1                +4^1       +4^1
         +4^0                     +4^0      +4^0         +4^0      +4^
+0      +4^0      +4^0         +4^0      +4^0      +4^0      +4^0     
+ +4^0      +4^0      +4^0      +4^0      +4^0
^0     1
^1     4    5
^2    16   17     20   21
^3    64   65     68   69      80   81   84   85
^4   256  257    260  261     272  273  276  277     320  321  324  32
+5  336  337  340  341
^5  1024 1025   1028 1029    1040 1041 1044 1045    1088 1089 1092 109
+3 1104 1105 1108 1109    1280 1281 1284 1285 1296 1297 1300 1301 1344
+ 1345 1348 1349 1360 1361 1364 1365
^6  4096 4097   4100 4101    4112 4113 4116 4117    4160 4161 4164 416
+5 4176 4177 4180 4181    4352 4353 4356 4357 4368 4369 4372 4373 4416
+ 4417 4420 4421 4432 4433 4436 4437 5120 512 ....
^7 16384 ...

[download]

That should be codable as recursive iterator routine with a nested loop -- though its not falling off the page for me -- but more importantly should be expressible as a formula in terms of N which would avoid the need to do any conversions.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Replies are listed 'Best First'.
Re^2: Can It Be Written In Base X With Only 1s And 0s
by Limbic~Region (Chancellor) on Jun 16, 2015 at 11:27 UTC
    BrowserUk,
    Yes, I noticed a pattern right away but no way to get to it. Starting from the fact that regardless of what base the number is written in, they must all follow: 
    10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111

    [download]
    Essentially what you get is the powerset of the sum of base X from 0 to the left most significant digit. Unfortunately, I can't think of way to benefit from this without memoization.

    Cheers - L~R

[reply]
[d/l]
      I can't think of way to benefit from this without memoization.

      It means that you can generate the list of compliant numbers rather than searching for them. See gen() in Re: Can It Be Written In Base X With Only 1s And 0s. Cuts the search space by 99%.

      If you combine that with my hypothesis that the numbers in the series will be sums of distinct powers of their consitutents and that cuts the search space by another 99%.

      That makes looking for candidates in all N power series very fast. I've searched upto (3/4/5/6)^25, in about half an hour. (Assuming that the next number will be sums of distinct powers.)

      Then the problem becomes the memory required to store the possible candidates from 3/4/5 whilst testing the 6^* range; which means getting selective about what you store and creative about how you store it.

      Of course it could be that my hypothisis is wrong which means going back and looking at all the sums of multiple power combinations; and that's 1000s of times slower.

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
        BrowserUk,
        I think you misinterpreted why I was creating this function in the first place. While I was inspired by the video, I am not attempting to use this function to try and find another number after 82000. This was mostly an interesting diversion - something I could give my employees to see what they came up with.

        I have given thought to how I would go about finding the next number in the sequence. What I would do is look for a pattern in the gaps between a couple of the bases. In other words, attempt to uncover a Least Common Multiple and then search for a base 6 that fits before testing further. I haven't tried it yet - given that I know how large these numbers are, I would need more time than I am currently willing to commit to making sure I haven't made a mistake.

        Cheers - L~R

[reply]

In Section Seekers of Perl Wisdom