Statistics

Problem Statement for "ASCIISum"

Problem Statement

Consider the following function: 

def f(n): return sum( ord(x) for x in str(n) )

(The function writes n as a string and then adds up the ASCII values of its digits.)

If we start from some positive integer n and repeatedly apply this function f, we will get an infinite sequence of positive integers. It's fairly obvious that for any starting number n this sequence must eventually become periodic. Perhaps more surprisingly, each of these sequences eventually becomes constant. Let final(n) denote that constant for the sequence starting with n.

Given the long N, sum final(i) over all i such that 1 <= i <= N, and return the result modulo 10^9 + 7.

Definition

Class:
ASCIISum
Method:
total
Parameters:
long
Returns:
int
Method signature:
int total(long N)
(be sure your method is public)

Notes

  • The ASCII values of the characters '0', '1', ..., '8', '9' are 48, 49, ..., 56, 57. (I.e., the character representing the digit x has ASCII value 48+x.)

Constraints

  • N will be between 1 and 10^18 - 1, inclusive.

Examples

  1. 3

    Returns: 465

    We have: f(1) = 49, f(49) = 109, f(109) = 154, and f(154) = 154 f(2) = 50, f(50) = 101, f(101) = 146, f(146) = 155, and f(155) = 155 f(3) = 51, f(51) = 102, f(102) = 147, f(147) = 156, and f(156) = 156 Hence, the sum final(1) + final(2) + final(3) equals 154 + 155 + 156.

  2. 6

    Returns: 930

    We now also have final(4) = 157, final(5) = 158, and final(6) = 150.

  3. 10

    Returns: 1543

    The next few values are final(7) = 151, final(8) = 152, final(9) = 153, and final(10) = 157.

  4. 999999999999

    Returns: 454936082

    Don't forget to do calculations modulo 10^9 + 7, and watch out for integer overflows.

  5. 1

    Returns: 154

  6. 2

    Returns: 309

  7. 4

    Returns: 622

  8. 5

    Returns: 780

  9. 7

    Returns: 1081

  10. 8

    Returns: 1233

  11. 9

    Returns: 1386

  12. 11

    Returns: 1701

  13. 47

    Returns: 7242

  14. 50

    Returns: 7704

  15. 98

    Returns: 15105

  16. 99

    Returns: 15255

  17. 100

    Returns: 15409

  18. 101

    Returns: 15564

  19. 400

    Returns: 61777

  20. 470

    Returns: 72597

  21. 990

    Returns: 153171

  22. 1670

    Returns: 257952

  23. 2024

    Returns: 312486

  24. 5217

    Returns: 804225

  25. 6627

    Returns: 1021371

  26. 6764

    Returns: 1042464

  27. 7333

    Returns: 1130089

  28. 7429

    Returns: 1144876

  29. 8048

    Returns: 1240209

  30. 8432

    Returns: 1299336

  31. 9395

    Returns: 1447638

  32. 9400

    Returns: 1448410

  33. 10082

    Returns: 1553514

  34. 11197

    Returns: 1726342

  35. 13101

    Returns: 2021457

  36. 23429

    Returns: 3622299

  37. 44577

    Returns: 6900246

  38. 51363

    Returns: 7952076

  39. 64857

    Returns: 10043637

  40. 73118

    Returns: 11324094

  41. 81655

    Returns: 12647329

  42. 87200

    Returns: 13506807

  43. 96327

    Returns: 14921496

  44. 134879

    Returns: 20863275

  45. 341221

    Returns: 52640929

  46. 349290

    Returns: 53883549

  47. 353806

    Returns: 54579016

  48. 476524

    Returns: 73477720

  49. 548475

    Returns: 84558225

  50. 563702

    Returns: 86903187

  51. 638918

    Returns: 98486451

  52. 648687

    Returns: 99990879

  53. 695138

    Returns: 107144340

  54. 1591882

    Returns: 245835292

  55. 2643279

    Returns: 408801828

  56. 3105533

    Returns: 480451203

  57. 4288054

    Returns: 663741958

  58. 5003365

    Returns: 774615163

  59. 6602383

    Returns: 22462943

  60. 6736361

    Returns: 43229533

  61. 6929950

    Returns: 73235831

  62. 7087422

    Returns: 97643995

  63. 7277484

    Returns: 127103605

  64. 9180000

    Returns: 421993576

  65. 23032361

    Returns: 557638470

  66. 39333809

    Returns: 71285745

  67. 40461759

    Returns: 245346126

  68. 43934875

    Returns: 780639160

  69. 54944005

    Returns: 478891041

  70. 61483060

    Returns: 488171932

  71. 78223645

    Returns: 72235342

  72. 82494799

    Returns: 731690443

  73. 87625098

    Returns: 524037271

  74. 97081599

    Returns: 984911024

  75. 218268043

    Returns: 767955607

  76. 407431950

    Returns: 88338414

  77. 479083493

    Returns: 194322632

  78. 547385546

    Returns: 781114416

  79. 552000000

    Returns: 496354033

  80. 605764849

    Returns: 829848739

  81. 749243544

    Returns: 68938490

  82. 824619612

    Returns: 752057755

  83. 899056097

    Returns: 289466869

  84. 929933621

    Returns: 75438207

  85. 930082628

    Returns: 98533155

  86. 977000000

    Returns: 370614496

  87. 3130000000

    Returns: 677381978

  88. 3200000000

    Returns: 515024247

  89. 3428304448

    Returns: 857708256

  90. 4270489159

    Returns: 294365249

  91. 4478760171

    Returns: 550279242

  92. 4613925365

    Returns: 488879532

  93. 5615392301

    Returns: 619795190

  94. 5935786196

    Returns: 269284207

  95. 6926484791

    Returns: 754334443

  96. 6993531860

    Returns: 146177385

  97. 7373499694

    Returns: 907797

  98. 9254961459

    Returns: 545715767

  99. 13562801771

    Returns: 245328718

  100. 17555614726

    Returns: 114982074

  101. 42542627060

    Returns: 862237054

  102. 46970178873

    Returns: 85326571

  103. 57037498277

    Returns: 339094459

  104. 69278583073

    Returns: 367930257

  105. 78330759201

    Returns: 183838408

  106. 81333541450

    Returns: 457374143

  107. 85688119977

    Returns: 314244961

  108. 99761352006

    Returns: 809990445

  109. 101906624755

    Returns: 174109057

  110. 238292262359

    Returns: 916700745

  111. 246451588969

    Returns: 573163362

  112. 294063871057

    Returns: 407456001

  113. 392521998319

    Returns: 52927692

  114. 478864926640

    Returns: 958322678

  115. 480403626660

    Returns: 455779854

  116. 531761900265

    Returns: 849512209

  117. 863932154392

    Returns: 968940542

  118. 962130587067

    Returns: 696396711

  119. 1174235385688

    Returns: 939528834

  120. 1362363163397

    Returns: 744869609

  121. 1731279375916

    Returns: 757409780

  122. 2182894423707

    Returns: 89327388

  123. 2300065276189

    Returns: 571334967

  124. 3154581619930

    Returns: 603687669

  125. 4187468912060

    Returns: 132847136

  126. 5125840281163

    Returns: 694039969

  127. 6950863780406

    Returns: 334442478

  128. 9640767985764

    Returns: 483354424

  129. 17581917485618

    Returns: 647215644

  130. 18618763455982

    Returns: 771497087

  131. 21358345247015

    Returns: 946134751

  132. 22464090501466

    Returns: 459374919

  133. 27331819668652

    Returns: 475007263

  134. 43652390177527

    Returns: 886175075

  135. 75000000000000

    Returns: 374646228

  136. 78900000000000

    Returns: 370414728

  137. 85281044372197

    Returns: 241181831

  138. 87107029246425

    Returns: 894705980

  139. 87395960093538

    Returns: 175695000

  140. 97111699913325

    Returns: 837220412

  141. 231806137687460

    Returns: 546067882

  142. 257232729705397

    Returns: 281260266

  143. 440938397808733

    Returns: 637956697

  144. 498278406100441

    Returns: 860957530

  145. 565531997396269

    Returns: 438840721

  146. 619338440154395

    Returns: 7970255

  147. 650854293542170

    Returns: 248880687

  148. 653104011302412

    Returns: 499277259

  149. 726585660831683

    Returns: 96586662

  150. 985921413588961

    Returns: 492585471

  151. 1596201445566226

    Returns: 786907715

  152. 2027976810261875

    Returns: 846257040

  153. 3207844065905003

    Returns: 190785918

  154. 4914373140816653

    Returns: 950507640

  155. 5250000000000000

    Returns: 759771288

  156. 5415349666278155

    Returns: 853480920

  157. 6079429370268331

    Returns: 251431719

  158. 7876223408569800

    Returns: 238637906

  159. 8059346922016260

    Returns: 624150189

  160. 8108706807840359

    Returns: 873330065

  161. 8418918002624759

    Returns: 728332920

  162. 13256145542801242

    Returns: 207295928

  163. 15892318405880456

    Returns: 124326555

  164. 24150068633666810

    Returns: 471552496

  165. 34055365922691622

    Returns: 523150873

  166. 37278898776059665

    Returns: 297664412

  167. 47939996356049836

    Returns: 628850132

  168. 49889199426211726

    Returns: 389057761

  169. 76216626080611616

    Returns: 255782990

  170. 76369150113546887

    Returns: 195261423

  171. 88531315084168852

    Returns: 445717093

  172. 909866993225851567

    Returns: 785189495

  173. 969561958374905840

    Returns: 307173023

  174. 977412436758596723

    Returns: 499555008

  175. 983365093431678143

    Returns: 745306980

  176. 986313052588867588

    Returns: 989820357

  177. 999999999999999995

    Returns: 848301653

  178. 999999999999999996

    Returns: 848301806

  179. 999999999999999997

    Returns: 848301960

  180. 999999999999999998

    Returns: 848302115

  181. 999999999999999999

    Returns: 848302271

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: