Statistics

Problem Statement for "Undiv2"

Problem Statement

Given a positive integer x, let s(x) be the second smallest positive integer that does not divide x.

For example, let x = 6. The integers that do not divide x are 4, 5, 7, 8, 9, 10, ... The second smallest of these is 5. Hence we have s(6) = 5.

Hero took a blank sheet of paper. For each i between 1 and n, inclusive, he computed the value s(i) and wrote it on the paper. You are given the int n. Compute and return the sum of the n numbers on Hero's paper.

Definition

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

Constraints

  • n will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 1

    Returns: 3

    The smallest two positive integers that don't divide 1 are 2 and 3. Thus, we have s(1) = 3.

  2. 2

    Returns: 7

  3. 3

    Returns: 11

    The answer is s(1) + s(2) + s(3) = 3 + 4 + 4 = 11.

  4. 5

    Returns: 19

  5. 8

    Returns: 32

  6. 13

    Returns: 53

  7. 148

    Returns: 629

  8. 43

    Returns: 181

  9. 209

    Returns: 889

  10. 134

    Returns: 569

  11. 95

    Returns: 402

  12. 219

    Returns: 934

  13. 250

    Returns: 1066

  14. 178

    Returns: 758

  15. 69

    Returns: 291

  16. 89

    Returns: 376

  17. 271

    Returns: 1157

  18. 275

    Returns: 1173

  19. 193

    Returns: 822

  20. 172

    Returns: 734

  21. 37

    Returns: 156

  22. 22

    Returns: 91

  23. 196

    Returns: 835

  24. 76

    Returns: 321

  25. 14

    Returns: 57

  26. 170

    Returns: 725

  27. 53630

    Returns: 229923

  28. 495253

    Returns: 2123356

  29. 813117

    Returns: 3486167

  30. 960118

    Returns: 4116430

  31. 199711

    Returns: 856240

  32. 595305

    Returns: 2552321

  33. 287090

    Returns: 1230874

  34. 579640

    Returns: 2485162

  35. 422175

    Returns: 1810032

  36. 324723

    Returns: 1392224

  37. 117401

    Returns: 503338

  38. 152474

    Returns: 653713

  39. 716812

    Returns: 3073275

  40. 218496

    Returns: 936781

  41. 420940

    Returns: 1804741

  42. 669556

    Returns: 2870670

  43. 931311

    Returns: 3992924

  44. 309337

    Returns: 1326258

  45. 867497

    Returns: 3719320

  46. 639439

    Returns: 2741544

  47. 314517004

    Returns: 1348470924

  48. 425746086

    Returns: 1825358297

  49. 470596795

    Returns: 2017652749

  50. 996872890

    Returns: 4274026834

  51. 218065286

    Returns: 934940539

  52. 19768625

    Returns: 84756665

  53. 948518086

    Returns: 4066708797

  54. 594405127

    Returns: 2548472823

  55. 504951108

    Returns: 2164944593

  56. 187256312

    Returns: 802849092

  57. 124633025

    Returns: 534355874

  58. 844596960

    Returns: 3621153834

  59. 146426417

    Returns: 627793607

  60. 222714612

    Returns: 954874222

  61. 366099053

    Returns: 1569625569

  62. 34113053

    Returns: 146257453

  63. 999999975

    Returns: 4287434013

  64. 999999983

    Returns: 4287434046

  65. 999999986

    Returns: 4287434060

  66. 1000000000

    Returns: 4287434122

  67. 999999999

    Returns: 4287434116

  68. 999999969

    Returns: 4287433988

  69. 927323880

    Returns: 3975840045

  70. 100000000

    Returns: 428743404

  71. 13424232

    Returns: 57555487

  72. 2333333

    Returns: 10004000

  73. 923456789

    Returns: 3959260151

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: