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

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

[download]

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

Replies are listed 'Best First'.
Re^2: Can It Be Written In Base X With Only 1s And 0s
by Laurent_R (Canon) on Jun 15, 2015 at 21:57 UTC
    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.

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

In Section Seekers of Perl Wisdom