4
$\begingroup$

I recently tackled the following problem, in a coding competition:

Let a rising number be a positive number whose decimal representation has no digit smaller than a previous digit.

For example, 445678 and 7789 are rising 101 and 94 are not.

The question was to find

$s(x)$ = $\sum$ of all rising numbers below $10^x$.

I could code it just fine (using dynamic programming), that's my area. What I cannot figure is the strange pattern of repeating digits that the answer has. See below.

Is there any mathematical insight that explain how those sequences of repeating digits appear ?

x, s(x)
1 45
2 1980
3 60885
4 1588158
5 37072035
6 794439360
7 15888877290
8 300123432180
9 5402222173062
10 93311111017800
11 1555185185015670
12 25122222221925780
13 394777777777276410 <- bunch of 7
14 6053259259258436016
15 90798888888887572305
16 1335277777777775721450
17 19287345679012342535175
18 274083333333333328619100
19 3837166666666666659721395 <- bunch of 6 and so on 
20 52989444444444444434376450
21 722583333333333333318953925
22 9739166666666666666646409200
23 129855555555555555555527376900
24 1714093333333333333333294594824
25 22415066666666666666666613991260
26 290565679012345679012345608114320
27 3735844444444444444444444349927580
28 47664222222222222222222222097341960
29 603746814814814814814814814651199428
30 7595524444444444444444444444231769760
31 94944055555555555555555555555281167235

(I'm 100% confident the results are right and not a bug ;-))

$\endgroup$
3
  • $\begingroup$ Nothing to do with the question, but values of $n$ such that the last digit of $s(n)$ is $5$ are equal to OEIS A103127 or OEIS A103192 for the first $8$ terms. $\endgroup$ Nov 3, 2021 at 19:06
  • 1
    $\begingroup$ @BillyJoe you can actually get a closed form expression for the last digit. It’s not difficult to show that $\sum$ones digit of all rising numbers below $10^x = 9\binom{x+9}{x}-\binom{x+9}{x+1}$, so the last digit of this is the same as the last digit of the sum in the question. The same method can be extended slightly, but I haven’t been able to extend it enough to answer the question $\endgroup$
    – iosce
    Nov 4, 2021 at 19:15
  • $\begingroup$ Seems worth linking this here in case anything relevant to this problem comes up, and also for BillyJoe’s much cleaner form of the expresion I found $x\binom{x+9}{8}$ $\endgroup$
    – iosce
    Nov 5, 2021 at 0:48

0

You must log in to answer this question.

Browse other questions tagged .