Statistics

Problem Statement for "ExploringNumbers"

Problem Statement

Vasa likes to construct sequences of numbers. If you tell him a positive integer n, he will begin a new sequence by writing the integer n as its first element. He will then repeat the following steps:

  1. If the last number in his sequence is a prime, he terminates the sequence.
  2. If he already wrote n elements without finding a prime, he becomes bored and leaves.
  3. Otherwise, he computes the next element of the sequence as the sum of squares of digits of the last element. For example, 4001 will be followed by 4^2 + 0^2 + 0^2 + 1^2 = 17, and 17 will be followed by 1^2 + 7^2 = 50.

Find out what happens for the given int n. If Vasa eventually becomes bored and leaves, return -1. Otherwise, return the length of the generated sequence.

Definition

Class:
ExploringNumbers
Method:
numberOfSteps
Parameters:
int
Returns:
int
Method signature:
int numberOfSteps(int n)
(be sure your method is public)

Notes

  • A prime number is a positive integer with exactly two positive integer divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11. Note that 1 is not a prime.

Constraints

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

Examples

  1. 5

    Returns: 1

    The input itself is a prime.

  2. 57

    Returns: 4

    Vasa will write down 57, 74 (= 5^2 + 7^2), 65 (= 7^2 + 4^2), and 61 (= 6^2 + 5^2). Number 61 is a prime.

  3. 1

    Returns: -1

    Vasa begins by writing down the number 1. As 1 is not a prime, he is not done yet. As he already wrote down 1 element of the sequence without finding a prime, he becomes bored and leaves.

  4. 6498501

    Returns: 2

  5. 989113

    Returns: 6

  6. 12366

    Returns: -1

    For n=12366 there are no primes among the first 12366 elements of Vasa's sequence.

  7. 999999999

    Returns: 7

  8. 1000000000

    Returns: -1

  9. 900000011

    Returns: 1

  10. 19112

    Returns: 10

  11. 999999991

    Returns: 4

  12. 999999997

    Returns: 4

  13. 25

    Returns: 2

  14. 34

    Returns: 3

  15. 2

    Returns: 1

  16. 3

    Returns: 1

  17. 4

    Returns: 3

  18. 5

    Returns: 1

  19. 6

    Returns: 4

  20. 7

    Returns: 1

  21. 8

    Returns: 4

  22. 9

    Returns: 4

  23. 1111111

    Returns: 2

  24. 998812807

    Returns: 6

  25. 997927811

    Returns: 5

  26. 998054383

    Returns: 2

  27. 999999987

    Returns: -1

  28. 17

    Returns: 1

  29. 999884959

    Returns: 1

  30. 982451653

    Returns: 1

  31. 49

    Returns: 2

  32. 40009

    Returns: 1

  33. 999999937

    Returns: 1

  34. 111121380

    Returns: -1

  35. 623610000

    Returns: -1

  36. 999000016

    Returns: -1

  37. 941110000

    Returns: -1

  38. 100000000

    Returns: -1

  39. 77

    Returns: 8

  40. 1162

    Returns: 6

  41. 900000008

    Returns: 7

  42. 999992573

    Returns: 1

  43. 952

    Returns: 3

  44. 999981110

    Returns: -1

  45. 999987511

    Returns: -1

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: