1Math::NumSeq::RepdigitRUasdeirx(C3o)ntributed Perl DocumMeanttha:t:iNounmSeq::RepdigitRadix(3)
2
6 Math::NumSeq::RepdigitRadix -- radix in which i is a repdigit
7
9 use Math::NumSeq::RepdigitRadix;
10 my $seq = Math::NumSeq::RepdigitRadix->new;
11 my ($i, $value) = $seq->next;
12
14 The radix in which i is a repdigit,
15 2, 0, 0, 2, 3, 4, 5, 2, 3, 8, 4, 10, etc
17 starting i=0
18 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 Is this behaviour for i=0,1,2 any good? Perhaps it will change.
25
27 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
28 classes.
29 "$seq = Math::NumSeq::RepdigitRadix->new ()"
31 Create and return a new sequence object.
32 Random Access
34 "$value = $seq->ith($i)"
35 Return the radix in which $i is a repdigit.
36 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
42 ith() Value
43 "ith()" looks for the smallest radix r for which there's a digit d and
44 length len satisfying
45 i = d * repunit(len)
47 i = d * (r^(len-1) + r^(len-2) + ... + r^2 + r + 1)
48 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 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 if no r_found then r_found = i-1
60 For a given d the radix r to give i would be
62 i/d = r^(len-1) + ... + r + 1
64 but it's enough to calculate
66 i/d = r^(len-1)
68 r = floor nthroot(i/d, len-1)
69 and then power up to see if it gives the desired i/d.
71 repunit(len) = r^(len-1) + ... + r + 1
73 = (r^len - 1) / (r-1)
74 check if equals i/d
75 floor(nthroot()) is never too small, since an r+1 from it would give
77 (r+1)^(len-1) = r^(len-1) + binomial*r^(len-2) + ... + 1
79 > r^(len-1) + r^(len-2) + ... + 1
80 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 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 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
99 Math::NumSeq, Math::NumSeq::RepdigitAny
100
102 <http://user42.tuxfamily.org/math-numseq/index.html>
103
105 Copyright 2010, 2011, 2012, 2013, 2014 Kevin Ryde
106 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 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 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/>.
119perl v5.28.1 2014-06-29 Math::NumSeq::RepdigitRadix(3)