/ 
Math-NumSeq-74
River stage zero No dependents
/ Math::NumSeq::RepdigitRadix

NAME

Math::NumSeq::RepdigitRadix -- radix in which i is a repdigit

SYNOPSIS

use Math::NumSeq::RepdigitRadix;
my $seq = Math::NumSeq::RepdigitRadix->new;
my ($i, $value) = $seq->next;

DESCRIPTION

The radix in which i is a repdigit,

2, 0, 0, 2, 3, 4, 5, 2, 3, 8, 4, 10, etc
starting i=0

i=0 is taken to be a repdigit "00" in base 2. i=1 and i=2 are not repdigits in any radix. Then i=3 is repdigit "11" in base 2. Any i>=3 is at worst a repdigit "11" in base i-1, but may be a repdigit in a smaller base. For example i=8 is "22" in base 3.

Is this behaviour for i=0,1,2 any good? Perhaps it will change.

FUNCTIONS

See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.

$seq = Math::NumSeq::RepdigitRadix->new ()

Create and return a new sequence object.

Random Access

$value = $seq->ith($i)

Return the radix in which $i is a repdigit.

The current code relies on factorizing $i and a hard limit of 2**32 is placed on $i in the interests of not going into a near-infinite loop.

FORMULAS

ith() Value

ith() looks for the smallest radix r for which there's a digit d and length len satisfying

i = d * repunit(len)
i = d * (r^(len-1) + r^(len-2) + ... + r^2 + r + 1)

The current approach is to consider repdigit lengths successively from log2(i) downwards and candidate digits d from among the divisors of i.

for len=log2(i) down to 2
  for d each divisor of i, descending
    r = nthroot(i/d, len-1)
    if r >= r_found then next len
    if r <= d then next divisor
    if (r^len-1)/(r-1) == i/d then r_found=r, next len

if no r_found then r_found = i-1

For a given d the radix r to give i would be

i/d = r^(len-1) + ... + r + 1

but it's enough to calculate

i/d = r^(len-1)
r = floor nthroot(i/d, len-1)

and then power up to see if it gives the desired i/d.

repunit(len) = r^(len-1) + ... + r + 1
             = (r^len - 1) / (r-1)
check if equals i/d

floor(nthroot()) is never too small, since an r+1 from it would give

(r+1)^(len-1) = r^(len-1) + binomial*r^(len-2) + ... + 1
              > r^(len-1) +          r^(len-2) + ... + 1

Divisors are taken in descending order so the radices r are in increasing order. So if a repdigit is found in a given len then it's the smallest of that length and can go on to other lengths.

The lengths can be considered in any order but the current code goes from high to low since a bigger length means a smaller maximum radix within that length (occurring when d=1, ie. a repunit), so it might establish a smaller "r_found" and a smaller r_found limits the number of divisors to be tried in subsequent lengths. But does that actually happen often enough to make any difference?

ith() Other Possibilities

When len is even the repunit part r^(len-1)+...+1 is a multiple of r+1. Can that cut the search? For a given divisor the r is found easily enough by nthroot, but maybe i with only two prime factors can never be an even length>=4 repdigit, or something like that.

SEE ALSO

Math::NumSeq, Math::NumSeq::RepdigitAny

HOME PAGE

http://user42.tuxfamily.org/math-numseq/index.html

LICENSE

Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.