JOIN
Get Time

   Problem Statement  

 Problem Statement for CoprimeNeighbors

Problem Statement

    

When little Limak played with numbers he noticed a surprising property: If two numbers are coprime, they like each other and want to spend time together. Otherwise, they hate each other and cannot be together. Limak has a good heart and he wants numbers to be happy.



You are given an int N. Limak asks you to find a sequence of N integers t[0], t[1], ..., t[N-1] with following properties:

  • Every element should be between 1 and 10^18, inclusive.
  • Each pair of consecutive elements must be coprime. In other words, for every i between 0 and N-2, inclusive, the greatest common divisor of t[i] and t[i+1] must be 1.
  • No other pairs of elements may be coprime. In other words, for every valid i and j such that i + 2 ? j the numbers t[i] and t[j] must have a common divisor greater than one.



Find any such sequence and return it as a long[]. (You may assume that for the given constraints a solution always exists.)

 

Definition

    
Class:CoprimeNeighbors
Method:findAny
Parameters:int
Returns:long[]
Method signature:long[] findAny(int N)
(be sure your method is public)
    
 

Constraints

-N will be between 2 and 500, inclusive.
 

Examples

0)
    
2
Returns: {14, 25 }
We are looking for a sequence with 2 elements: t[0] and t[1]. The values t[0] and t[1] are supposed to be coprime. The values 14 and 25 are coprime, so {14, 25} is a valid sequence.
1)
    
3
Returns: {1000000000000000000, 1, 1000000000000000000 }

Note that the sequence is not cyclic: the first element and the last element are not adjacent. For N=3 the numbers t[0] and t[2] cannot be coprime.



Also note that the returned sequence may contain duplicates.

2)
    
6
Returns: {14, 39, 80, 63, 26, 105 }

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 706 Round 1 - Division I, Level Three