Statistics

Problem Statement for "CrossPrimesOut"

Problem Statement

Consider an infinite sequence of digits. For example, here's the prefix of sqrt(47), with the decimal point removed: 6855654600401044124935871449084848960460643461001326275485108185678...

Now consider a simple infinite process. During the process we maintain an infinite text. Initially, this text consists of our infinite sequence of digits. Then, for each prime, in increasing order, we do the following:

  • Find the first occurrence of the prime in the current infinite text.
  • If we did find it, replace it by spaces. (If the entire infinite text contains no occurrences of the current prime, nothing happens.)

After the entire infinite process is done, we are left with a collection of space-separated tokens. We convert them back into numbers to obtain the result: a sequence of non-negative integers.


You are given an int X that is not a square and a int N.

Determine and return the N-th term (0-based index) of the sequence produced by the above process if we start with the decimal expansion of sqrt(X). Return its value modulo 10^9 + 7.

Definition

Class:
CrossPrimesOut
Method:
findTerm
Parameters:
int, int
Returns:
int
Method signature:
int findTerm(int X, int N)
(be sure your method is public)

Notes

  • Spaces matter. For example, "1234 789" does NOT contain an occurrence of "47".

Constraints

  • X will be between 1 and 10,000, inclusive.
  • X will not be a square.
  • N will be between 0 and 30, inclusive.

Examples

  1. 47

    1

    Returns: 5654600

    We start with sqrt(47): 6855654600401044124935871449084848960460643461001326275485108185678... We find and remove the first 2: 68556546004010441 4935871449084848960460643461001326275485108185678... We find and remove the first 3: 68556546004010441 49 5871449084848960460643461001326275485108185678... We find and remove the first 5: 68 56546004010441 49 5871449084848960460643461001326275485108185678... Now the same with 7, 11, 13, and so on. Immediately before processing the prime 401 we have the following: 68 565460040104 49 58 144908484 604606 4 00 26275485108185 8... Removing the first occurrence of 401 produces: 68 5654600 04 49 58 144908484 604606 4 00 26275485108185 8 At this point it's easy to show that in the final sequence element 0 will be 68 and element 1 will be 5654600. Thus, we return 5654600.

  2. 47

    2

    Returns: 4

    The final token at index 2 in the sequence for sqrt(47) is "04", as seen in the previous example. When converted into an integer, the leading zero is obviously lost.

  3. 47

    9

    Returns: 0

    Here the actual string token produced by the infinite process is "00".

  4. 5

    10

    Returns: 270897077

    The actual term is 24,270,897,245.

  5. 2

    0

    Returns: 1

  6. 5

    0

    Returns: 2

  7. 351

    30

    Returns: 522

  8. 11

    30

    Returns: 44

  9. 5765

    2

    Returns: 9128665

  10. 7049

    17

    Returns: 215

  11. 7433

    18

    Returns: 989

  12. 5628

    8

    Returns: 3

  13. 8396

    12

    Returns: 36

  14. 6430

    19

    Returns: 12648303

  15. 671

    25

    Returns: 0

  16. 6858

    21

    Returns: 92

  17. 388

    30

    Returns: 958908

  18. 1679

    0

    Returns: 60

  19. 4323

    30

    Returns: 5

  20. 7890

    23

    Returns: 928

  21. 8957

    0

    Returns: 946

  22. 5171

    18

    Returns: 6

  23. 7008

    7

    Returns: 8890

  24. 3896

    16

    Returns: 7

  25. 8421

    11

    Returns: 5

  26. 7246

    30

    Returns: 7

  27. 3966

    1

    Returns: 9

  28. 9191

    11

    Returns: 50

  29. 5791

    19

    Returns: 9089

  30. 5602

    17

    Returns: 680822

  31. 9423

    24

    Returns: 92740

  32. 3211

    7

    Returns: 79574

  33. 579

    4

    Returns: 57

  34. 5472

    3

    Returns: 8

  35. 5945

    18

    Returns: 0

  36. 6285

    16

    Returns: 385

  37. 8850

    26

    Returns: 31

  38. 4143

    3

    Returns: 0

  39. 3719

    29

    Returns: 0

  40. 5487

    6

    Returns: 606

  41. 7718

    23

    Returns: 2

  42. 1805

    24

    Returns: 5

  43. 6827

    19

    Returns: 98204

  44. 5785

    21

    Returns: 560

  45. 4692

    28

    Returns: 88

  46. 3916

    25

    Returns: 6

  47. 9098

    29

    Returns: 492

  48. 4286

    11

    Returns: 6

  49. 8728

    18

    Returns: 5

  50. 658

    15

    Returns: 38

  51. 5116

    18

    Returns: 5080314

  52. 6480

    8

    Returns: 44

  53. 8510

    25

    Returns: 866

  54. 3620

    19

    Returns: 64

  55. 1867

    20

    Returns: 25

  56. 3393

    12

    Returns: 4

  57. 7953

    8

    Returns: 4204

  58. 9889

    29

    Returns: 0

  59. 9143

    26

    Returns: 1

  60. 7273

    25

    Returns: 182064

  61. 2791

    29

    Returns: 958

  62. 1357

    25

    Returns: 42

  63. 4355

    29

    Returns: 2158

  64. 8960

    28

    Returns: 5325

  65. 7138

    27

    Returns: 1874665

  66. 544

    29

    Returns: 5061

  67. 4342

    30

    Returns: 812

  68. 9972

    29

    Returns: 54

  69. 7731

    30

    Returns: 28525668

  70. 5161

    25

    Returns: 267

  71. 9453

    26

    Returns: 48

  72. 3463

    27

    Returns: 2305

  73. 7072

    30

    Returns: 2

  74. 3015

    26

    Returns: 6

  75. 7698

    26

    Returns: 8608560

  76. 2096

    25

    Returns: 9585

  77. 2240

    30

    Returns: 5

  78. 9333

    27

    Returns: 97260069

  79. 8641

    28

    Returns: 183

  80. 1771

    27

    Returns: 2

  81. 7274

    25

    Returns: 623205404

  82. 2006

    28

    Returns: 89

  83. 1101

    27

    Returns: 105

  84. 340

    27

    Returns: 589355285

  85. 684

    26

    Returns: 404158

  86. 2969

    30

    Returns: 3

  87. 8384

    28

    Returns: 3441

  88. 3296

    28

    Returns: 4266

  89. 8656

    28

    Returns: 25

  90. 9235

    29

    Returns: 1

  91. 164

    30

    Returns: 49

  92. 1210

    26

    Returns: 2

  93. 2467

    29

    Returns: 25

  94. 5544

    30

    Returns: 1680

  95. 765

    29

    Returns: 880

  96. 3843

    30

    Returns: 8

  97. 1004

    28

    Returns: 21

  98. 2018

    25

    Returns: 6

  99. 1452

    27

    Returns: 183033

  100. 883

    29

    Returns: 9908

  101. 3918

    29

    Returns: 124602547

  102. 8764

    26

    Returns: 825

  103. 9011

    29

    Returns: 8

  104. 4476

    29

    Returns: 327492045

  105. 9353

    25

    Returns: 174660

  106. 9224

    28

    Returns: 32

  107. 5616

    29

    Returns: 83

  108. 855

    25

    Returns: 50

  109. 939

    30

    Returns: 830

  110. 39

    18

    Returns: 472590610

  111. 301

    9

    Returns: 581032462

  112. 10

    30

    Returns: 333

  113. 197

    30

    Returns: 4

  114. 6055

    28

    Returns: 8553

  115. 9994

    30

    Returns: 864974285

  116. 9993

    30

    Returns: 40

  117. 1147

    30

    Returns: 36545

  118. 9997

    30

    Returns: 252

  119. 9707

    27

    Returns: 12248078

  120. 7624

    10

    Returns: 212

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: