### Can It Be Written In Base X With Only 1s And 0s

by Limbic~Region (Chancellor)
 on Jun 15, 2015 at 17:21 UTC Need Help??

Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All,
I recently watched this youtube video talking about the sequence 2, 3, 4, 82000. 82000 is the smallest integer that when written in base 2, 3, 4 and 5 is done so only with 1s and 0s. I tried to come up with an easy way to test if a number in base 10 would be written with only 1s and 0s in another base without fully converting the number. I came up with the following (untested as I am without access to Perl at the moment).

Can you come up with a more efficient way working with the constraint that you aren't converting completely between bases?

```sub only_1_0_in_base_x {
my (\$num, \$base) = @_;
if (\$num / \$base != int(\$num / \$base)) {
\$num--;
return 0 if \$num / \$base != int(\$num / \$base);
}
my \$exponent = int(log(\$num) / log(\$base));

my \$max = 0;
\$max += \$base ** \$_ for 1 .. \$exponent;

return 0 if \$num > \$max;

while (\$exponent) {
my \$next = \$base ** \$exponent;
return 1 if \$next == \$num;

\$num -= \$next if \$num > \$next;
\$max -= \$next;

return 0 if \$num > \$max;
}
}

Cheers - L~R

Replies are listed 'Best First'.
Re: Can It Be Written In Base X With Only 1s And 0s
by ikegami (Patriarch) on Jun 15, 2015 at 19:26 UTC

The following uses an iterator that returns the next highest sum of powers of the largest base. It then checks if that sum consists of just ones and zeroes in the other bases.

```use strict;
use warnings;

use Math::BigInt qw( );

# Skips over 0 and 1.
sub make_iter {
my (\$base) = @_;

my \$num = Math::BigInt->new(1);
my @digits = 1;  # -1 represents zero.
my @powers = Math::BigInt->new(1);

return sub {
if (\$digits[-1] > 0) {
push @digits, -1;
push @powers, \$powers[-1] * \$base;
}

for (0..\$#digits) {
\$digits[\$_] = -\$digits[\$_];
\$num += \$digits[\$_] * \$powers[\$_];
return \$num if \$digits[\$_] > 0;
}
};
}

sub test {
my (\$num, \$base) = @_;
while (\$num > 0) {
my \$digit = \$num % \$base;
return 0 if \$digit > 1;
\$num = (\$num - \$digit)/\$base;
}

return 1;
}

{
my \$i = \$ARGV[0] || 5;

my \$candidate_num;
my \$num;
my \$iter = make_iter(\$i);
CANDIDATE:
while (1) {
\$num = \$iter->();

if (++\$candidate_num == 10_000) {
\$candidate_num = 0;
print("> \$num\n");
}

for my \$base (reverse 3..\$i-1) {
next CANDIDATE if !test(\$num, \$base);
}

last;
}

print("\$num\n");
}

Note: If f(6) exists, it must have more than 2184 digits in base 10[Reference]. As such, I included support for large numbers.

```sub make_iter {
my (\$base) = @_;

my \$num = Math::BigInt->new(1);
my @digits = 1;  # -1 represents zero.
my @powers = Math::BigInt->new(1);

return sub {
if (\$digits[-1] > 0) {
push @digits, -1;
push @powers, \$powers[-1] * \$base;
}

for (0..\$#digits) {
\$digits[\$_] = -\$digits[\$_];
\$num += \$digits[\$_] * \$powers[\$_];
return \$num if \$digits[\$_] > 0;
}
};
}
is probably faster as
```sub make_iter {
my (\$base) = @_;

my \$num = Math::BigInt->new(1);

return sub {
\$num->binc;
return Math::BigInt->new( \$num->as_bin() =~ s/^0?b//r );
};
}
with a fast back-end.
```return Math::BigInt->new( \$num->as_bin() =~ s/^0?b//r );

It seems to be taking the binary representation, and making a new object in base 10, and returning that?

-QM
--
Quantum Mechanics: The dreams stuff is made of

Re: Can It Be Written In Base X With Only 1s And 0s
by GotToBTru (Prior) on Jun 15, 2015 at 18:25 UTC

Rearranged .. might not be more efficient. I think yours might detect some early signs that the test will eventually fail that mine misses.

```(\$num,\$base) = @ARGV;
\$orig = \$num;
\$exp = int(log(\$num)/log(\$base));
while (\$exp) {
\$try = \$base ** \$exp--;
if (\$try > \$num) {
\$bin .= "0"; next
}
\$num -= \$try if (\$try <= \$num);
die "Nope!" if (\$try <= \$num);
\$bin .= "1"
}
if (\$num > 1) {
die "Nope!"
} else {
\$bin .= \$num ? "1" : "0";
print "\$orig in base \$base: \$bin\n";
}

Update: written as subroutine that returns 1 if the number can be expressed purely in 1's and 0's:

```sub hp_only_1_0_in_base_x {
(\$num,\$base) = @_;
\$exp = int(log(\$num)/log(\$base));
while (\$exp) {
\$try = \$base ** \$exp--;
next if (\$try > \$num);
\$num -= \$try;
return 0 if (\$try <= \$num);
}
return (\$num > 1) ? 0 : 1
}

Update 2: removed superfluous test in line 7

Dum Spiro Spero
Re: Can It Be Written In Base X With Only 1s And 0s
by ikegami (Patriarch) on Jun 15, 2015 at 18:42 UTC

Seems to me it would be cheaper to actually convert the number.

```sub test {
my (\$num, \$base) = @_;
while (\$num > 0) {
my \$digit = \$num % \$base;
return 0 if \$digit > 1;
\$num = (\$num - \$digit)/\$base;
}

return 1;
}

Takes at most floor(logb(n)) loop passes, just like what you were attempting.

And, in addition, it seems to me that if you do the full conversion, then you might be able to reduce considerably the number of numbers that you need to check. Suppose for example that, in base 4, you find one number to be 20000001. Then you know that there is no point to check any number between 20000001(4) and 33333333(4), as none of them is a likely candidate to be made of only 0's and 1's.

This huge optimization might be possible without doing the full conversion, but it looks far less easy.

That's what the iterator in my other post does. If you're looking for the 5th term, it will produce the following sequence:

105
115
1005
1015
1105
1115
10005
...
1111115
10000005
...

Re: Can It Be Written In Base X With Only 1s And 0s
by BrowserUk (Patriarch) on Jun 15, 2015 at 21:16 UTC

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   ...

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 ...

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
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
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

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
Re: Can It Be Written In Base X With Only 1s And 0s
by BrowserUk (Patriarch) on Jun 16, 2015 at 00:20 UTC

This finds your sample, 82000 in a split second:

```#! perl -slw
use strict;

sub gen{
my( \$n, \$p ) = @_;
return 1 if \$p == 0;
my @n = gen( \$n, \$p - 1 );
my \$v = \$n**\$p;
return @n, \$v, map{ \$v + \$_ } @n;
}

our \$LIMIT //= 10;
our \$N //= 5;

my %tests;
for( 3 .. \$N ) {
++\$tests{ \$_ } for gen( \$_, \$LIMIT );
}

\$tests{ \$_ } == \$N-2 and print for sort{ \$a <=> \$b } keys %tests;

__END__
C:\test>1130506
1
82000

To go much higher you'd probably have to convert the recursive generator to an iterator to avoid memory problems.

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
What is interesting is that on line 17, \$_ is 2 different entities:
```for( 3 .. \$N ) {
++\$tests{ \$_ } for gen( \$_, \$LIMIT );
}

-QM
--
Quantum Mechanics: The dreams stuff is made of

What is interesting is that on line 17, \$_ is 2 different entities:

Yes, but both are distinct at their point of use.

It's a trick -- if you want to call it that -- that I learned a long time ago from Merlyn. Same variable name but two different scopes in a single line.

The value from the outer for loop is passed into gen() and that must be executed before the list is available to the inner for loop, so there is no conflict.

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
Re: Can It Be Written In Base X With Only 1s And 0s
by BrowserUk (Patriarch) on Jun 16, 2015 at 01:17 UTC

82000 is a sum of powers of all the inputs

```3^0 +           3^3 + 3^4 + 3^5 + 3^6 + 3^7 +      3^9 + 3^10 == 82000
4^2 + 4^3 +                   4^7 + 4^8             == 82000
5^3 + 5^4 + 5^5 +       5^7                   == 82000

And I suspect that the next number in the sequence will contain:

```                6^3 +                   6^7                   + 6^11 +
+ ??? == ???

Which means it'll be big!

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

In order to find the next element I consulted The on-line encyclopedia of integer sequences. Funnily enough they only have the sequence up to 82000. There is a reference to this paper where the author claims that the next number would be at least 10**21 according to his experiments.

I can atest to it being greater than 95367431640625.

Even assuming that my "sum of single powers" hypothesis is correct; I think it will take more cpu power than I'm prepared to expend to look much beyond that.

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
Actually, it says at least 102184, as I previously mentioned.
82000 is a sum of powers of all the inputs
That's sort of by definition: if the number is expressed with only 1 and 0 in a given base, then it will be sum of simple powers of that base.

Hm. A phraseology problem I think.

Below are all the numbers less than 3^11, that when encoded base-3 use only 0 1:

All of them can be defined as the sums of multiples of powers of 3. But only the first number in each block is a power of 3.

And 82000 is a sum of a selection of those first numbers in each block. And that is so for 4 & 5 also.

And, if it holds true for the higher numbers in the sequence (and they are going to be very large) then not having to consider all the other numbers in each of those blocks is a significant saving.

So worth pointing out don't you think? Even if I need to clarify the meaning or use better phraseology.

How about a sum of single powers? Or discrete powers?

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

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1130506]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others avoiding work at the Monastery: (3)
As of 2024-03-01 03:54 GMT
Voting Booth?
My favourite way to spend a leap day ...

Results (28 votes). Check out past polls.