Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.6

On Repdigit Polygonal Numbers

Mike Keith
4100 Vitae Springs Road
Salem, OR 97306
Email address: domnei@aol.com

Abstract: We consider the problem of determining which polygonal numbers are repdigits (numbers consisting of a single repeated digit). An efficient algorithm for finding repdigit polygonal numbers is presented and used to provide a complete characterization of all 1526 such numbers with 50 or fewer digits. Several other new and intriguing integer sequences (such as the sequence of so-called primitive solutions) are also introduced.

1. Introduction

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.

2. Finding RP Numbers, and the Combination Sequence

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.

3. Primitive Repdigit Polygonal Numbers

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.

 

 

References

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


Return to Journal of Integer Sequences home page