 |
Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.6 |
|
|
Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.6 |
The polygonal numbers are illustrated in the figure below. The nth k-sided polygonal number, P(k,n), is the number of counters that can be arranged into a k-sided polygon with n counters along each side.
n=2 3 4 k=2 oo ooo oooo 2 3 4 ... o o o o k=3 o o o o o o o o o o o o o o o 3 6 10 ... o o o o o o o o o o o k=4 o o o o o o o o o o o o o o o o o o 4 9 16 ... o o o o o o o o o o o k=5 o o o o o o o o o o o o o o o o o o o o o o o o o o o o 5 12 22 ...
Figure 1. The first few polygonal numbers
A formula for P(k,n) is:
| P(k,n) = n((k-2)(n-1) + 2)/2 | (n>=2 and k>=2) | (1) |
A repdigit is a number, like 3 or 55 or 999999, consisting of repetitions of a single digit. Some polygonal numbers are also repdigits, such as P(5,4)=22 shown in Figure 1, or more dramatically
P(8925662618878671, 387) = 666666666666666666666.
In this paper we consider some properties of these repdigit polygonal (RP) numbers as well as some new integer sequences which result from their study.
The primary problem is to determine which polygonal numbers are also repdigits. The converse is easy - every repdigit number is trivially a polygonal number, because every integer r is equal to both P(2,r) and P(r,2), as can be seen by the fact that the first row and column of Figure 1 are just the integers in order. However, nontrivial representations are also possible, as shown by (see Figure 1)
P(2,22) = P(5,4) = P(22,2) = 22
or
P(2,666) = P(3,36) = P(46,6) = P(223,3) = P(666,2) = 666.
We define the combination number of a given repdigit r, c(r), to be the number of pairs n, k such that P(n,k) = r. The above examples show that c(22)=3 and c(666)=5. The combination sequence is the sequence of combination numbers pertaining to the successive repdigits (which are 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222, 333, etc., sequence A010785 in the On-Line Encyclopedia of Integer Sequences).
Here is an efficient procedure for computing the combination number of a given repdigit. Every repdigit is just some decimal digit, d, times a repunit number (a number of the form 111...1). We denote the repunit with m decimal digits by Rm. Then equation (1) becomes
dRm = n((k-2)(n-1) + 2)/2
Solving for k, we get
k = ( (2dRm)/n + 2n - 4 )/(n-1)
Denote the quotient (2dRm)/n by the symbol q. For a given Rm to be a polygonal number, we see that it is necessary and sufficient that the two following conditions hold:
| 2dRm = 0 (mod n), | (a) | ||
| q + 2n - 4 = 0 (mod n-1). | (b) |
Condition (a) is required for q to be an integer, and (b) is required for k to be an integer. Note that (b) can be rewritten as
| q = 2 (mod n-1). | (b') |
Condition (a) means that the only possible values of n are the divisors of 2dRm. We must therefore factorize Rm. Fortunately, the prime factorizations of the repunits can be readily obtained from a number of sources, or calculated easily (at least for the first hundred or so repunits) using modern factorization algorithms. We assume that a table of repunit factorizations is provided. We can now find all (k,n) pairs such that P(k,n) equals a given repdigit number dRm by the following simple procedure:
Put all the prime factors of R(m) in a list. Adjoin 2 and the prime factors of d. Form all possible divisors n of 2*d*R(m) by taking all combinations of primes from this list. For each trial divisor n, compute q. If q = 2 mod (n-1), this is a success: (k,n) is an RP number.
This algorithm must be programmed in a language that supports arbitrary-precision arithmetic. We used UBASIC, and were able to find all repdigit polygonal numbers with 50 or fewer decimal digits in a couple of hours on a home PC. From this we can tabulate the first 500 values of the combination sequence (A033618), which are as follows:
d 1 2 3 4 5 6 7 8 9 m 1 0 1 2 2 2 3 2 2 3 2 2 3 3 2 4 5 2 3 3 3 4 3 4 3 4 5 3 3 3 4 3 2 3 3 3 6 3 2 3 5 2 3 3 3 3 4 2 3 3 6 7 3 4 3 4 5 4 3 4 7 2 2 3 3 3 4 3 3 3 8 3 4 3 2 3 6 2 3 3 9 6 3 4 3 4 5 4 3 3 10 3 2 3 3 3 5 3 2 4 11 2 3 3 3 4 4 2 3 3 12 6 3 5 3 6 5 4 3 3 13 5 2 3 3 3 4 3 3 3 14 3 4 3 2 3 6 2 3 3 15 5 3 4 3 4 5 3 4 3 16 5 3 5 3 3 5 4 2 3 17 2 3 3 3 3 4 2 3 3 18 6 3 4 4 4 5 5 3 3 19 2 2 3 3 3 4 3 3 3 20 3 4 3 2 4 6 3 3 3 21 5 3 4 3 4 7 3 3 3 22 3 2 3 3 3 5 3 2 3 23 2 3 3 3 3 4 2 3 3 24 6 3 4 3 4 5 4 4 3 25 3 2 3 3 3 4 3 3 3 26 3 4 3 2 3 6 2 3 5 27 6 4 4 3 4 5 4 3 3 28 4 2 4 3 3 5 3 2 3 29 3 3 3 3 4 4 2 3 3 30 6 3 4 3 4 5 4 3 5 31 2 2 3 3 3 4 3 3 3 32 3 4 3 2 3 6 3 3 3 33 6 3 4 3 4 5 4 3 3 34 3 2 3 3 3 5 3 2 3 35 2 3 3 3 4 4 2 3 3 36 9 3 5 3 4 5 5 3 4 37 2 2 3 3 3 4 3 3 3 38 3 4 3 2 4 6 3 3 3 39 5 3 4 3 4 6 3 3 3 40 4 2 3 3 3 5 4 2 3 41 3 3 3 3 3 4 2 3 3 42 6 3 6 3 4 5 4 3 4 43 3 2 3 3 3 4 3 3 3 44 3 4 3 3 3 6 2 3 4 45 7 3 4 3 4 6 7 3 3 46 4 2 3 3 3 6 3 2 3 47 2 3 3 3 4 4 2 3 3 48 6 3 4 3 4 6 5 3 3 49 4 2 3 3 3 4 3 3 3 50 3 4 3 2 3 6 2 3 3
Table 1. c(r), the number of ways of expressing each repdigit, r = dRm ,
as a polygonal number.
Every term in this sequence (after the first two) is at least 2, since every repdigit number r equals both P(r,2) and P(2,r). The largest term so far in this sequence is the (unique) 9 at m=36, d=1. This says that there are 9 different ways of representing the number 11111 11111 11111 11111 11111 11111 11111 1 as a polygonal number. The value 8 does not yet occur, although presumably it will eventually. The average of all the terms in the sequence so far is close to 3 (about 3.06).
Here are a few related sequences. Summing up each row, we obtain the number of polygonal numbers which are m-digit repdigits (for m=1, 2, 3, ..., A033702):
17 27 32 28 26 37 26 29 35 28 27 38 29 29 34 33 26 37 26 31 35 27 26 36 27 31 36 29 28 37 26 30 35 27 27 41 26 31 34 29 27 38 27 31 40 29 27 37 28 29
The partial sums of this sequence give the number of polygonal numbers which are repdigits with m or fewer digits (A033703):
RPN(m) = 17 44 76 104 130 167 193 222 257 285 312 350 379 408 442 475 501 538 564 595 630 657 683 719 746 777 813 842 870 907 933 963 998 1025 1052 1093 1119 1150 1184 1213 1240 1278 1305 1336 1376 1405 1432 1469 1497 1526
In particular, there are precisely 1526 distinct repdigit polygonal numbers with 50 or fewer digits.
So far we have not actually displayed a listing of the 1526 repdigit polygonal numbers with 50 or less digits. The reason for this is that we can describe these numbers using a much smaller list, by recognizing that many of these RP numbers are related.
For example, consider:
P(2,3) = 33
P(12,3) = 333
P(112,3) = 3333
etc.
and
P(5,4) = 22
P(3705,4) = 22222
P(3703705,4) = 22222222
etc.
In both cases, as we shall see below, there is an infinite sequence of RP numbers, where n remains constant, k steadily increases and the repdigit number has the same base digit d but gets p digits longer at each step. We refer to p as the period of the infinite RP number sequence.
In turns out that almost every repdigit polygonal number is a member of one of these infinite sequences. We call the first term in such a sequence the primitive RP number. We distinguish between two types: a simple primitive RP number, in which k=2 or n=2, and a fancy primitive number (the rest). The reason for this distinction is that all the simple primitives are obvious (since the k=2 and n=2 polygonal numbers are just the integers in order), and hence the fancy primitives are the only ones that really need to be enumerated.
Before enumerating all the primitive RP numbers less than 1050, we first explain why these infinite sequences of solutions occurs.
Suppose we have any RP number, which as we have seen must satisfy conditions (a) and (b'). Also, n is a product of certain prime divisors of 2dRm. In general n will consist of zero or more factors of 2d combined with zero or more factors of Rm.
Lemma 1: If Rm is the smallest repunit divisible by a prime f, then Rcm is also divisible by f, for all c >= 1.
Proof: By induction on c. If Rcm is divisible by f, then so is R(c+1)m , because
R(c+1)m = 10mRcm + Rm
and both terms on the right side are divisible by f (by the induction hypothesis).
For example, the 3rd repunit, 111, factors as 3 x 37. Both of these factors are present in the 6th repunit, 111111 (which = 3 x 7 x 11 x 13 x 37), the 9th repunit 111111111 (which = 3 x 3 x 37 x 333667), and so on.
Consider now our RP number, for which n contains a subset of the prime factors of the repunit Rm. Although m may not be the smallest index in which each of these prime factors occurs, we know from the lemma that each prime factor in this subset will occur among the higher repunits with some period. Define Prep to be the LCM of all these periods. Then it must be the case that every Prep-th repunit after this one is divisible by n, since each of these contains the prime factors needed for n to divide it evenly.
In summary: if we start from a given RP number and form larger ones in which d and n remain the same and the length of the repunit increases in steps of Prep, every one of these will satisfy condition (a).
Example: consider P(41139,74)=111111111. Since n = 74 = 2 x 37, and the 2 can be obtained from 2d, the only repunit factor n contains is 37. We know from the previous example that 37 occurs as a prime factor of every 3rd repunit (because the lowest repunit in which it appears is R3); therefore Prep = 3. This means that 111111111111 and every 3rd repunit thereafter will be divisible by 37, and will therefore satisfy condition (a). For instance, 2 x 111111111111 is exactly divisible by 74.
What about condition (b')?
We have a series of repunits which satisfy condition (a): r0 = Rm, r1 = Rm+Prep, r2 = Rm+2Prep, etc., and at the first step condition (b') is satisfied: q = 2dr0/n = 2 mod n-1. We ask: what is the sequence of q values (q0, q1, q2, ...) that correspond to the repdigits r0, r1, r2, ...? To answer this, note that each repunit in the sequence is related to the previous one by
ri = 10Prepri-1 + RPrep ,
i.e.
(2dri)/n = (2d10Prepri-1)/n + (2dRPrep)/n ,
or
qi = qi-110Prep + q0 mod 10Prep
For (b') to be satisifed we need qi = 2 mod n-1 for some larger i. This will be the case (and there will be an infinite sequences of cases for which it is true) if the following condition holds:
Ring Period Condition: Working in the ring of integers mod n-1, start with the value 2 and successively apply the linear recurrence qi = aqi-1 + b, where a = 10Prep mod n-1 and b = (q0 mod 10Prep) mod n-1. If the sequence of values q0 (= 2) -> q1 -> q2 -> ... eventually returns to the value 2 (which means it satisfies condition (b')) then the primitive repdigit polygonal number under consideration generates an infinite sequence of RP numbers.
We refer to the period with which 2 repeats in the sequence of q's as the ring period Pring. Because the sequence of q's is itself spaced with a period of Prep within the repdigits, the full period with which additional RP numbers appear beyond a primitive one is the product of these two periods: p = PrepPring.
Continuing the previous example, we may now determine the sequence of RP numbers generated by the primitive solution P(41139,74)=111111111, for which Prep = 3. We compute a = 103 mod 73 = 51 and b = ((2 x 111111111)/74 mod 103 ) mod 73 = 2. Starting with 2 and applying the function 51x + 2 iteratively, we produce:
starting value: 2 51*2+2 = 104 = 31 mod 73 51*31+2 = 1583 = 50 mod 73 51*50+2 = 2552 = 70 mod 73 51*70+2 = 3572 = 68 mod 73 51*68+2 = 3470 = 39 mod 73 51*39+2 = 1991 = 20 mod 73 51*20+2 = 1022 = 0 mod 73 51*0 +2 = 2 = 2 mod 73
so Pring = 8. The full period for this primitive solution is therefore 3 x 8 = 24. We obtain the following sequence of RP numbers:
P(41139,74) = 111111111
P(41137027438397301411000041139,74) = 111111111111111111111111111111111
etc.
where each repdigit in the sequence (and, consequently, each value of k) is 24 digits longer than the previous one.
We can now concisely describe all RP numbers of 50 digits or less. First, take all those which are generated by the simple primitive solutions with k=2 and n equal to some repdigit number. Here are the periods of the small simple primitive solutions:
Value of d m 1 2 3 4 5 6 7 8 9 1 1 3 1 1 3 6 ** 2 2 6 ** 42 54 6 18 84 42 3 6 48 123 663 69 18 96 2658 498 4 12 2220 336 2220 2776 420 972 17772 1428 5 20 36990 480 31710 33810 495 4860 49380 3205
Table 2. Periods of the simple primitive RP numbers 3,4,5,...99999 with k=2.
All of the larger simple primitive solution have a period of at least 498, and so are not relevant for RP numbers with 50 digits or less. There is one exception: the d=1 primitives, all of which (as can be seen from the table) have relatively small periods. In fact, it is easy to show that those solutions have a period of exactly m(m-1).
In addition to these simple primitives, we also have to consider the remaining simple primitives, which are simply those of the form k=d, n=2, repdigit=d, and all the RP numbers generated by these (which are of the form k=ddd...d, n=2, repdigit=ddd...d).
Finally, take all those generated by the fancy primitive solutions. Table 3 below gives the complete list of fancy primitive RP numbers of 50 digits or less (A033704 and A033705) with their periods.
k n RP number Period 3 3 6 1 4 3 9 1 5 4 22 3 3 10 55 9 3 11 66 2 16 4 88 3 38 3 111 3 9 6 111 3 75 3 222 3 11 9 333 3 149 3 444 3 186 3 555 3 3 36 666 6 260 3 777 3 297 3 888 3 9 44 6666 42 1589 8 44444 6 531 21 111111 6 131 42 111111 30 1475 33 777777 6 514 63 999999 30 41139 74 111111111 24 21604940 9 777777777 9 65359479 18 9999999999 16 170677592 63 333333333333 30 933706818 35 555555555555 48 5378862 455 555555555555 678 806321563 53 1111111111111 78 360633274 79 1111111111111 78 199660579 106 1111111111111 78 3220611916266 24 888888888888888 66 63890006966 187 1111111111111111 240 975514583945 68 2222222222222222 528 8944083 27302 3333333333333333 104368 34829977467 438 3333333333333333 792 57189542483662 17 7777777777777777 16 1610305958132047 24 444444444444444444 66 8925662618878671 387 666666666666666666666 1344 3561667376774099913 707 888888888888888888888888 96 880855486848827581349 477 99999999999999999999999999 624 77645779951859616429849 54 111111111111111111111111111 351 633111744222855333966447 27 222222222222222222222222222 54 8210180623973727422003286 29 3333333333333333333333333333 84 2183081749534812567698 3191 11111111111111111111111111111 812 233754090696587190275829829 93 999999999999999999999999999999 330 56287290329843521332883037 189 999999999999999999999999999999 138 9649728635845433403776352377 402 777777777777777777777777777777777 6600 884149845715851922583839509122 355 55555555555555555555555555555555555 6090 10943672915503901419394377140858 143 111111111111111111111111111111111111 210 2178649237472766884531590413943357 18 333333333333333333333333333333333333 48 2959580585151361407069169626247251820 73 7777777777777777777777777777777777777777 72 3265092891892774349430241290364710878 83 11111111111111111111111111111111111111111 205 3630844752340079442883181200938210286 429 333333333333333333333333333333333333333333 318 74681483472987707427820346223357380773 173 1111111111111111111111111111111111111111111 903 25972676744065243363981091891330320502833 93 111111111111111111111111111111111111111111111 330 4357298474945533769063180827886710239651418 18 666666666666666666666666666666666666666666666 48 103662238808180431531091267196824973714220 123 777777777777777777777777777777777777777777777 60 411305012045361067042716963393853927962867 62 777777777777777777777777777777777777777777777 60 408040686552937566510631908128823341235 1953 777777777777777777777777777777777777777777777 180 254200666005744935051729835532169094283029 94 1111111111111111111111111111111111111111111111 690 65662037493023408516366262845136084572704293 143 666666666666666666666666666666666666666666666666 210 39067230797479382268946630256007563415882394 239 1111111111111111111111111111111111111111111111111 336
Table 3. All fancy primitive repdigit polygonal numbers less than 1050.
As an example, we derive the entry in Table 1 which says that there are 9 manifestations of r = 11111 11111 11111 11111 11111 11111 11111 1 (36 1's) as an RP number. First, there is the simple primitive solution (k,n) = (r, 2). Looking at Table 2, we see that the simple primitive solution (11,2) has period 2, so it generates solutions with any even number of digits, including 36. The 6-digit simple primitive solution (111111,2), which is just beyond the end of Table 2, has, as described earlier, period 6 x 5 = 30, so it also generates a 36-digit solution. There is also the obvious simple primitive solution (2, r).
To complete the list, look in Table 3 for RP numbers consisting of 1's with the correct period so that a 36-digit solution can be generated. We find five possibilities: (38,3) and (9,6) with length 3 and period 3, (531,21) with length 6 and period 6, (131,42) with length 6 and period 30, and the n=143 36-digit solution. Thus all nine solutions can be found from Tables 2 and 3.
Two of the simple primitive solutions (the ones marked with **: (2,9) and (2,33)) in Table 2 do not have finite ring periods, and so do not generate any additional solutions. For example, for (2,9) the recurrence gets stuck in a cycle of length one at the value 6. Are there other solutions with this property?
Note from Table 3 that one of the "fancy" things about the fancy primitives is the progression of k values, which also form an interesting sequence, A033706 (as do the values of n, A033707):
3, 4, 5, 3, 3, 16, 38, 9, 75, 11, 149, 186, 3, 260, 297, 9, 1589, 531, 131, 1475, 514, 41139, 21604940, ...
It has been noted since 1979 (see [2]) that all primitive RP numbers with k>2 tend to have large k and small n. (If a primitive solution has this property, then all RP numbers derived from it will also. So this is equivalent to saying that all RP numbers with k>2 tend to have large k and small n.)
In particular, the following conjecture, made in [2], is now strongly supported by the numerical evidence in Table 3 (although we still do not have a proof).
Conjecture. The only RP numbers with k > 2 and n > k are P(3,10), P(3,11), P(3,36), and P(9,44).
A related conjecture comes from defining the wickedness of an RP number to be the value of n/k.
Conjecture. The most wicked RP number with k>2 is the "Beast number", 666 = (3,36), with n/k = 12.
Another remarkable solution in Table 3 is (8944083, 27302) = 3333333333333333, whose k value is the largest among the fancy primitives so far.
Finally, define a simple RP number to be one generated from a simple (or trivial) primitive solution, and a fancy RP number to be one generated from a fancy primitive solution. What is the distribution of simple versus fancy RP numbers? Here are the two sequences (number of RP numbers of m digits, A033708, and their partial sums, A033709) for simple:
Numbers with exactly m digits: 15 21 21 24 21 22 24 24 22 24 21 22 24 24 22 25 21 22 24 25 23 24 21 22 25 24 22 25 21 22 24 24 22 24 21 23 24 25 23 25 21 22 24 26 23 24 21 22 25 24
Numbers with m or fewer digits: 15 36 57 81 102 124 148 172 194 218 239 261 285 309 331 356 377 399 423 448 471 495 516 538 563 587 609 634 655 677 701 725 747 771 792 815 839 864 887 912 933 955 979 1005 1028 1052 1073 1095 1120 1144
and fancy (A033710 and A033711) RP numbers :
Numbers with exactly m digits: 2 6 11 4 5 15 2 5 13 4 6 16 5 5 12 8 5 15 2 6 12 3 5 14 2 7 14 4 7 15 2 6 13 3 6 18 2 6 11 4 6 16 3 5 17 5 6 15 3 5
Numbers with m or fewer digits: 2 8 19 23 28 43 45 50 63 67 73 89 94 99 111 119 124 139 141 147 159 162 167 181 183 190 204 208 215 230 232 238 251 254 260 278 280 286 297 301 307 323 326 331 348 353 359 374 377 382
As can be seen from these sequences, there are many fewer fancy RP numbers than simple ones. Of the 1526 RP numbers with 50 digits or less, only 382 (= 25.03%) are fancy ones.
[1] D. W. Ballew and R. C. Weger, "Repdigit Triangular Numbers", Journal of Recreational Mathematics, Vol. 8, No. 2, p. 96, 1975.
[2] M. Keith, "Repdigit Polygonal Numbers", Journal of Recreational Mathematics, Vol. 12, No. 1, p. 9, 1979.
Received May 20, 1998; published in Journal of Integer Sequences May 25, 1998.