|
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.
| [reply]
[d/l] |
|
|
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.
| [reply]
[d/l]
[select] |
|
|
I'm confused about this line:
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
| [reply]
[d/l] |
|
|
|
|
|
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
| [reply]
[d/l]
[select] |
Re: Can It Be Written In Base X With Only 1s And 0s
by ikegami (Patriarch) on Jun 15, 2015 at 18:42 UTC
|
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.
| [reply]
[d/l] |
|
|
| [reply] |
|
|
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
...
| [reply] |
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.
| [reply]
[d/l]
[select] |
|
|
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.
| [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.
| [reply] |
|
|
|
|
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.
| [reply]
[d/l] |
|
|
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
| [reply]
[d/l]
[select] |
|
|
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.
| [reply] |
Re: Can It Be Written In Base X With Only 1s And 0s
by BrowserUk (Patriarch) on Jun 16, 2015 at 01:17 UTC
|
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.
| [reply]
[d/l]
[select] |
|
|
| [reply] |
|
|
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.
| [reply] |
|
|
Actually, it says at least 102184, as I previously mentioned.
| [reply] |
|
|
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.
| [reply] |
|
|
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.
| [reply]
[d/l] |
|
|
|
|
|
|
|
|
|