Statistics

Problem Statement for "EllysFractions"

Problem Statement

A positive common fraction is a fraction of the form A/B, where A and B are positive integers. An irreducible fraction is a positive common fraction such that A and B are relatively prime. (In other words, the only positive integer that divides both A and B is 1.)
Elly recently invented the factor fractions: A factor fraction is an irreducible fraction such that the product A*B is a factorial number (see Notes for definition). We will only be interested in factor fractions that lie strictly between 0 and 1. (That is, A must be strictly smaller than B.)

Examples:

  • 2/3, 4/6, 4/7, 7/7, 6/1, 42/49 are six positive common fractions
  • Out of those six, the following three are irreducible: 2/3, 4/7, 6/1.
  • The fraction 2/3 is a factor fraction, because 2*3 = 6 and that is a factorial number.
  • The fraction 4/7 is not a factor fraction, because 4*7 = 28 and that is not a factorial number.
  • The fraction 6/1 is a factor fraction, because 6*1 = 6 and that is a factorial number. However, as 6/1 does not lie strictly between 0 and 1, we are not interested in this fraction.
  • Note that 4/6 is not a factor fraction. (We do have 4*6=24, but a factor fraction has to be irreducible.)

You are given an int N. Compute and return the number of factor fractions A/B such that 0 < A/B < 1 and A*B is one of the factorial numbers from 1! to N! (inclusive).

Definition

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

Notes

  • The factorial of X, denoted X!, is the product of the first X positive integers. For example, 6! is 1*2*3*4*5*6 = 720. The factorial numbers are the numbers of the form X! for positive integer X. The smallest few: 1, 2, 6, 24, 120, 720, ...
  • The answer will always fit in a 64-bit signed integer.

Constraints

  • N will be between 1 and 250, inclusive.

Examples

  1. 1

    Returns: 0

    We are interested in factor fractions such that A*B = 1. The only positive common fraction with this property is the fraction 1/1. However, this fraction is not strictly between 0 and 1.

  2. 2

    Returns: 1

    Here the only valid factor fraction is 1/2.

  3. 3

    Returns: 3

    The three fractions are 1/2, 1/6, and 2/3. (We have 1*2 = 2! and 1*6 = 2*3 = 3!.)

  4. 5

    Returns: 9

  5. 100

    Returns: 177431885

    Plenty of fractions here.

  6. 250

    Returns: 61048957984531789

  7. 249

    Returns: 56545358357161293

  8. 248

    Returns: 52041758729790797

  9. 97

    Returns: 127100237

  10. 199

    Returns: 144809898763597

  11. 241

    Returns: 20516561338197325

  12. 42

    Returns: 25933

  13. 218

    Returns: 1094787945162061

  14. 85

    Returns: 30631245

  15. 170

    Returns: 2423142966605

  16. 225

    Returns: 1798475386938701

  17. 229

    Returns: 3065112782136653

  18. 109

    Returns: 1049847117

  19. 213

    Returns: 742944224273741

  20. 215

    Returns: 883681712629069

  21. 206

    Returns: 391100503385421

  22. 146

    Returns: 103860626765

  23. 32

    Returns: 5453

  24. 78

    Returns: 9659725

  25. 212

    Returns: 672575480096077

  26. 242

    Returns: 25020160965567821

  27. 246

    Returns: 43034559475049805

  28. 193

    Returns: 48052875519309

  29. 187

    Returns: 23863619708237

  30. 142

    Returns: 69500888397

  31. 105

    Returns: 445867341

  32. 153

    Returns: 258479449421

  33. 154

    Returns: 292839187789

  34. 43

    Returns: 34125

  35. 133

    Returns: 20108764493

  36. 172

    Returns: 2972898780493

  37. 217

    Returns: 1024419200984397

  38. 219

    Returns: 1165156689339725

  39. 198

    Returns: 109625526674765

  40. 227

    Returns: 2220687852004685

  41. 22

    Returns: 845

  42. 39

    Returns: 15693

  43. 120

    Returns: 6150120781

  44. 163

    Returns: 911314478413

  45. 168

    Returns: 1873387152717

  46. 50

    Returns: 124237

  47. 36

    Returns: 9549

  48. 145

    Returns: 95270692173

  49. 204

    Returns: 320731759207757

  50. 62

    Returns: 746829

  51. 73

    Returns: 4416845

  52. 84

    Returns: 26436941

  53. 174

    Returns: 4072410408269

  54. 165

    Returns: 1186192385357

  55. 4

    Returns: 5

  56. 119

    Returns: 5613249869

  57. 48

    Returns: 91469

  58. 8

    Returns: 29

  59. 38

    Returns: 13645

  60. 110

    Returns: 1318282573

  61. 224

    Returns: 1657737898583373

  62. 30

    Returns: 3405

  63. 29

    Returns: 2893

  64. 67

    Returns: 1533261

  65. 191

    Returns: 34858735985997

  66. 93

    Returns: 85157197

  67. 107

    Returns: 647193933

  68. 41

    Returns: 21837

  69. 15

    Returns: 173

  70. 149

    Returns: 138220365133

  71. 197

    Returns: 92033340630349

  72. 56

    Returns: 288077

  73. 141

    Returns: 60910953805

  74. 230

    Returns: 3628062735557965

  75. 121

    Returns: 6686991693

  76. 101

    Returns: 210986317

  77. 7

    Returns: 21

  78. 102

    Returns: 244540749

  79. 144

    Returns: 86680757581

  80. 49

    Returns: 107853

  81. 130

    Returns: 13666313549

  82. 124

    Returns: 8297604429

  83. 205

    Returns: 355916131296589

  84. 91

    Returns: 68379981

  85. 127

    Returns: 10445088077

  86. 182

    Returns: 12868503430477

  87. 59

    Returns: 419149

  88. 195

    Returns: 65645061563725

  89. 190

    Returns: 30460689474893

  90. 74

    Returns: 5465421

  91. 83

    Returns: 22242637

  92. 180

    Returns: 8470456919373

  93. 116

    Returns: 4002637133

  94. 140

    Returns: 52321019213

  95. 159

    Returns: 567717094733

  96. 181

    Returns: 10669480174925

  97. 228

    Returns: 2502162828715341

  98. 57

    Returns: 320845

  99. 137

    Returns: 30846182733

  100. 175

    Returns: 4622166222157

  101. 244

    Returns: 34027360220308813

  102. 247

    Returns: 47538159102420301

  103. 245

    Returns: 38530959847679309

  104. 131

    Returns: 15813797197

  105. 211

    Returns: 602206735918413

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: