Statistics

Problem Statement for "TheLuckyBasesDivOne"

Problem Statement

John and Brus believe that the digits 4 and 7 are lucky and all others are not. According to them, a lucky number is a number that contains only lucky digits in its decimal representation.

Recently, they became interested in numeral systems with different bases. Normally, people use the numeral system with base 10 to represent numbers, however, there exist numeral systems with other bases. More exactly, for each integer B, B >= 2, there exists a numeral system with base B. In this system, there are B different digits, used to represent numbers from 0 to B-1, inclusive. In order to represent a positive integer A in such system, it's necessary to find such digits a[n], a[n-1], ..., a[0], that A = a[n] * B^n + a[n-1] * B^(n-1) + ... + a[0] * B^0 (here ^ denotes the power operator), and then write these digits from left to right, in this exact order. For example, 255 = 4 * 52 + 47, therefore representation of number 255 in the numeral system with base 52 consists of two digits, the leftmost digit is 4 and the rightmost digit is 47.

The base of numeral system B is called lucky for some integer number A if all digits of the number A represented in numeral system with base B are the lucky numbers (i.e. 4, 7, 44, 47, ...). For example, base 52 is lucky for the number 255.

You are given a long n. Return the total number of lucky bases for the number n. If there are infinitely many such lucky bases, return -1 instead.

Definition

Class:
TheLuckyBasesDivOne
Method:
find
Parameters:
long
Returns:
long
Method signature:
long find(long n)
(be sure your method is public)

Constraints

  • n will be between 1 and 10^16, inclusive.

Examples

  1. 255

    Returns: 2

    There are two lucky bases for the number 255: 52 and 62.

  2. 474

    Returns: -1

    All bases greater than 474 are lucky.

  3. 13

    Returns: 0

    No lucky bases here.

  4. 4748

    Returns: 5

  5. 17

    Returns: 0

  6. 23

    Returns: 0

  7. 52

    Returns: 1

  8. 347723696

    Returns: 150

  9. 925643275

    Returns: 233

  10. 65038986

    Returns: 108

  11. 644199585

    Returns: 226

  12. 333393417

    Returns: 148

  13. 255248223

    Returns: 145

  14. 683104052

    Returns: 234

  15. 517788483

    Returns: 200

  16. 434727064

    Returns: 211

  17. 610370488

    Returns: 200

  18. 454765462

    Returns: 203

  19. 643862778

    Returns: 208

  20. 852497597

    Returns: 211

  21. 7099619347723696

    Returns: 27854

  22. 7883257925643275

    Returns: 27884

  23. 8116120065038986

    Returns: 29844

  24. 9656914644199585

    Returns: 29004

  25. 5693912333393417

    Returns: 25142

  26. 7572215255248223

    Returns: 29116

  27. 5678191683104052

    Returns: 25828

  28. 4768164517788483

    Returns: 25566

  29. 6954493434727064

    Returns: 28369

  30. 5033728610370488

    Returns: 25732

  31. 9099619347697918

    Returns: 27979

  32. 9883257925626617

    Returns: 27641

  33. 9116120065015927

    Returns: 27917

  34. 9656914644197045

    Returns: 27828

  35. 9693912333378931

    Returns: 29140

  36. 10000000000000000

    Returns: 28302

  37. 7777777777777777

    Returns: -1

  38. 7777777777777778

    Returns: 28182

  39. 4774747477474774

    Returns: -1

  40. 7

    Returns: -1

  41. 7099619347723696

    Returns: 27854

  42. 7883257925643275

    Returns: 27884

  43. 8116120065038986

    Returns: 29844

  44. 9656914644199585

    Returns: 29004

  45. 5693912333393417

    Returns: 25142

  46. 7572215255248223

    Returns: 29116

  47. 5678191683104052

    Returns: 25828

  48. 419546186871

    Returns: 1588

  49. 64969059354121

    Returns: 6951

  50. 32553584898247

    Returns: 4661

  51. 45395562278

    Returns: 786

  52. 37892149639977

    Returns: 5602

  53. 21270484151041

    Returns: 3611

  54. 69945385747222

    Returns: 7288

  55. 73048617291088

    Returns: 7219

  56. 100458529411078

    Returns: 7036

  57. 124394104724

    Returns: 892

  58. 5994467456372

    Returns: 3566

  59. 4997301456

    Returns: 397

  60. 10868313348334

    Returns: 3474

  61. 4451382129015250

    Returns: 26566

  62. 853639853734029

    Returns: 14907

  63. 158532595550982

    Returns: 6964

  64. 293296577135859

    Returns: 9465

  65. 4267871896654374

    Returns: 26081

  66. 2384185791015624

    Returns: 17610

  67. 1286948916285415

    Returns: 13751

  68. 2384185791015624

    Returns: 17610

  69. 126267109331844

    Returns: 7073

  70. 3566375989313287

    Returns: 19815

  71. 1086735827140

    Returns: 1736

  72. 631542762657

    Returns: 1757

  73. 31316926201

    Returns: 585

  74. 9999999800000004

    Returns: 28629

  75. 9999999999999999

    Returns: 28794

  76. 9999999999999998

    Returns: 27988

  77. 9999999999999997

    Returns: 29036

  78. 9999999999999996

    Returns: 28612

  79. 9999999999999995

    Returns: 27700

  80. 9999999999999994

    Returns: 29058

  81. 9999999999999993

    Returns: 29019

  82. 9999999999999992

    Returns: 27683

  83. 9999999999999991

    Returns: 28831

  84. 9598500211500004

    Returns: 27782

  85. 9876542873161235

    Returns: 27758

  86. 4704747470000774

    Returns: 25365

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: