Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

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

by Limbic~Region (Chancellor)
on Jun 15, 2015 at 17:21 UTC ( [id://1130506] : perlquestion . print w/replies, xml ) 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.
        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

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