Statistics

Problem Statement for "AvoidFour"

Problem Statement

It is a known fact that of all numbers, 4 is the one that brings the worst luck. It is for this reason that when generating number sequences, we need to avoid patterns related to the number 4 as much as possible.

You are given a long n. Count the number of positive integers that satisfy all of the following conditions:

  • The number contains at most n digits.
  • The number does not contain four consecutive '4' digits. For example, 43444124 is allowed, but 45444474 is not.
  • The number of digits in the number is not a multiple of any of the integers greater than 10 that contain only '4' in their decimal representations (44, 444, 4444, 44444, ...).

Return the total count of these numbers modulo 1000000007.

Definition

Class:
AvoidFour
Method:
count
Parameters:
long
Returns:
int
Method signature:
int count(long n)
(be sure your method is public)

Constraints

  • n will be between 1 and 40000000000 (4e10), inclusive.

Examples

  1. 4

    Returns: 9998

    Of all the 9999 positive integers containing 1, 2, 3 or 4 digits, 4444 is the only one that contains four consecutive '4' digits.

  2. 5

    Returns: 99980

    The numbers to ignore are: 4444, 44440, 44441, 44442, ..., 44449, 14444, 24444, 34444, 54444, ... , 94444.

  3. 87

    Returns: 576334228

  4. 88

    Returns: 576334228

    88 is a multiple of 44, so all numbers with 88 digits are ignored.

  5. 4128

    Returns: 547731225

  6. 124235233

    Returns: 450715451

  7. 12423442312

    Returns: 123527064

  8. 40000000000

    Returns: 403544996

  9. 12345612345

    Returns: 20960721

  10. 5235533

    Returns: 765857807

  11. 1212121212

    Returns: 768964375

  12. 21990232555

    Returns: 403032192

  13. 12228821822

    Returns: 477554622

  14. 6447712037

    Returns: 376573559

  15. 8073844796

    Returns: 761111360

  16. 5783623550

    Returns: 587096534

  17. 1807404079

    Returns: 490532649

  18. 29611455945

    Returns: 191714315

  19. 35180076445

    Returns: 782092064

  20. 20120108249

    Returns: 822533749

  21. 10893832830

    Returns: 255023821

  22. 11651476690

    Returns: 766005837

  23. 15468092273

    Returns: 812195616

  24. 4884

    Returns: 210493466

  25. 1

    Returns: 9

  26. 34359738368

    Returns: 643694717

  27. 34359738367

    Returns: 957658113

  28. 9038402876

    Returns: 763474046

  29. 31893635726

    Returns: 688734791

  30. 74

    Returns: 278144199

  31. 32

    Returns: 30190092

  32. 7

    Returns: 9996299

  33. 93

    Returns: 135211704

  34. 85

    Returns: 949544466

  35. 317

    Returns: 93343172

  36. 243

    Returns: 688951137

  37. 699

    Returns: 752702118

  38. 946

    Returns: 264393876

  39. 321

    Returns: 226136547

  40. 3500

    Returns: 752802741

  41. 4933

    Returns: 142178909

  42. 4606

    Returns: 686144286

  43. 6034

    Returns: 219915012

  44. 8776

    Returns: 631585663

  45. 51483

    Returns: 448697209

  46. 50514

    Returns: 389370082

  47. 72451

    Returns: 825438325

  48. 66652

    Returns: 493196037

  49. 93642

    Returns: 524340823

  50. 281019

    Returns: 3209496

  51. 376332

    Returns: 215058437

  52. 784848

    Returns: 239219938

  53. 409027

    Returns: 964656345

  54. 268763

    Returns: 734441952

  55. 3987451

    Returns: 535175259

  56. 5857402

    Returns: 879937535

  57. 7155817

    Returns: 806448713

  58. 3972740

    Returns: 28191424

  59. 4158281

    Returns: 92842090

  60. 38077138

    Returns: 210733721

  61. 46301347

    Returns: 169293426

  62. 46312434

    Returns: 233207425

  63. 42375156

    Returns: 384808146

  64. 71781953

    Returns: 998641866

  65. 966435215

    Returns: 450967466

  66. 259677529

    Returns: 276608087

  67. 334507712

    Returns: 399231167

  68. 871452297

    Returns: 512943692

  69. 497304209

    Returns: 792368826

  70. 8208477840

    Returns: 781715876

  71. 1154892128

    Returns: 943046852

  72. 9170386076

    Returns: 89244117

  73. 4334094703

    Returns: 871428832

  74. 1320912122

    Returns: 629733010

  75. 27655026219

    Returns: 615319089

  76. 16946347606

    Returns: 938727117

  77. 37744112749

    Returns: 242850654

  78. 35459749691

    Returns: 887520760

  79. 13741905231

    Returns: 760825989

  80. 21349399602

    Returns: 903069362

  81. 9907145697

    Returns: 631008825

  82. 12885196370

    Returns: 151446149

  83. 28805065336

    Returns: 851363187

  84. 27559234713

    Returns: 678644655

  85. 2633540365

    Returns: 115472565

  86. 34166345646

    Returns: 900878584

  87. 39358551595

    Returns: 622093845

  88. 35802772425

    Returns: 653000819

  89. 18784266286

    Returns: 831338744

  90. 7847238840

    Returns: 674860310

  91. 17956033142

    Returns: 337937489

  92. 12701773268

    Returns: 455179837

  93. 7887224628

    Returns: 946956564

  94. 7214014953

    Returns: 124256406

  95. 31810905501

    Returns: 336439205

  96. 29288141115

    Returns: 749665702

  97. 34374754809

    Returns: 461616098

  98. 32175804742

    Returns: 412023161

  99. 12649519850

    Returns: 468834453

  100. 5656

    Returns: 317574755

  101. 39999999997

    Returns: 512730467

  102. 21704497

    Returns: 893208456

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: