5
Task
Given positive integer n
, output a(n)
where a
is the sequence defined below:
a(n)
is the smallest positive integer not yet appeared so that the sum of the first n
elements in the sequence is divisible by n
.
Example
a(1)
is1
because it is the smallest positive integer that has not appeared in the sequence, and1
is divisible by1
.a(10)
is16
because look at the first nine elements:1,3,2,6,8,4,11,5,14
. They sum up to54
, so for the first ten elements to sum up to a multiple of10
,a(10)
would need to have a remainder of6
when divided by10
.6
has already appeared, soa(10)
is16
instead.
Testcases
n a(n)
1 1
2 3
3 2
4 6
5 8
6 4
7 11
8 5
9 14
10 16
11 7
12 19
13 21
14 9
15 24
16 10
17 27
18 29
19 12
20 32
100 62
1000 1618
10000 16180
What values of n and a(n) must we support? – Rohan Jhunjhunwala – 2016-08-18T01:42:02.150
@RohanJhunjhunwala Theoretically every positive number. – Leaky Nun – 2016-08-18T01:44:31.887
so bignum mandatory? – Rohan Jhunjhunwala – 2016-08-18T01:47:20.170
@RohanJhunjhunwala I said theoretically, meaning it is not mandatory. – Leaky Nun – 2016-08-18T01:47:37.463
so less than 2^31 -1 is ok? – Rohan Jhunjhunwala – 2016-08-18T01:49:28.623
I only ask so I can use int in Java (and S.I.L.O.S) – Rohan Jhunjhunwala – 2016-08-18T01:49:46.800
@RohanJhunjhunwala Yes. – Leaky Nun – 2016-08-18T01:50:51.980
Strangely related. – xnor – 2016-08-18T04:07:34.383