1Math::NumSeq::RepdigitRUasdeirx(C3o)ntributed Perl DocumMeanttha:t:iNounmSeq::RepdigitRadix(3)
2
3
4

NAME

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

SYNOPSIS

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

DESCRIPTION

14       The radix in which i is a repdigit,
15
16           2, 0, 0, 2, 3, 4, 5, 2, 3, 8, 4, 10, etc
17           starting i=0
18
19       i=0 is taken to be a repdigit "00" in base 2.  i=1 and i=2 are not
20       repdigits in any radix.  Then i=3 is repdigit "11" in base 2.  Any i>=3
21       is at worst a repdigit "11" in base i-1, but may be a repdigit in a
22       smaller base.  For example i=8 is "22" in base 3.
23
24       Is this behaviour for i=0,1,2 any good?  Perhaps it will change.
25

FUNCTIONS

27       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
28       classes.
29
30       "$seq = Math::NumSeq::RepdigitRadix->new ()"
31           Create and return a new sequence object.
32
33   Random Access
34       "$value = $seq->ith($i)"
35           Return the radix in which $i is a repdigit.
36
37           The current code relies on factorizing $i and a hard limit of 2**32
38           is placed on $i in the interests of not going into a near-infinite
39           loop.
40

FORMULAS

42   ith() Value
43       "ith()" looks for the smallest radix r for which there's a digit d and
44       length len satisfying
45
46           i = d * repunit(len)
47           i = d * (r^(len-1) + r^(len-2) + ... + r^2 + r + 1)
48
49       The current approach is to consider repdigit lengths successively from
50       log2(i) downwards and candidate digits d from among the divisors of i.
51
52           for len=log2(i) down to 2
53             for d each divisor of i, descending
54               r = nthroot(i/d, len-1)
55               if r >= r_found then next len
56               if r <= d then next divisor
57               if (r^len-1)/(r-1) == i/d then r_found=r, next len
58
59           if no r_found then r_found = i-1
60
61       For a given d the radix r to give i would be
62
63           i/d = r^(len-1) + ... + r + 1
64
65       but it's enough to calculate
66
67           i/d = r^(len-1)
68           r = floor nthroot(i/d, len-1)
69
70       and then power up to see if it gives the desired i/d.
71
72           repunit(len) = r^(len-1) + ... + r + 1
73                        = (r^len - 1) / (r-1)
74           check if equals i/d
75
76       floor(nthroot()) is never too small, since an r+1 from it would give
77
78           (r+1)^(len-1) = r^(len-1) + binomial*r^(len-2) + ... + 1
79                         > r^(len-1) +          r^(len-2) + ... + 1
80
81       Divisors are taken in descending order so the radices r are in
82       increasing order.  So if a repdigit is found in a given len then it's
83       the smallest of that length and can go on to other lengths.
84
85       The lengths can be considered in any order but the current code goes
86       from high to low since a bigger length means a smaller maximum radix
87       within that length (occurring when d=1, ie. a repunit), so it might
88       establish a smaller "r_found" and a smaller r_found limits the number
89       of divisors to be tried in subsequent lengths.  But does that actually
90       happen often enough to make any difference?
91
92   ith() Other Possibilities
93       When len is even the repunit part r^(len-1)+...+1 is a multiple of r+1.
94       Can that cut the search?  For a given divisor the r is found easily
95       enough by nthroot, but maybe i with only two prime factors can never be
96       an even length>=4 repdigit, or something like that.
97

SEE ALSO

99       Math::NumSeq, Math::NumSeq::RepdigitAny
100

HOME PAGE

102       <http://user42.tuxfamily.org/math-numseq/index.html>
103

LICENSE

105       Copyright 2010, 2011, 2012, 2013, 2014 Kevin Ryde
106
107       Math-NumSeq is free software; you can redistribute it and/or modify it
108       under the terms of the GNU General Public License as published by the
109       Free Software Foundation; either version 3, or (at your option) any
110       later version.
111
112       Math-NumSeq is distributed in the hope that it will be useful, but
113       WITHOUT ANY WARRANTY; without even the implied warranty of
114       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
115       General Public License for more details.
116
117       You should have received a copy of the GNU General Public License along
118       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
119
120
121
122perl v5.28.0                      2014-06-29    Math::NumSeq::RepdigitRadix(3)
Impressum