Consider the sequence `a(1) = 7, a(n) = a(n-1) + gcd(n, a(n-1)) for n >= 2`: 

`7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69, 72, 73...`.

Let us take the differences between successive elements of the sequence and
get a second sequence `g: 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1...`.

For the sake of uniformity of the lengths of sequences **we add** a `1` at the head of g:

`g: 1, 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1...`

Removing the 1s gives a third sequence:
`p: 5, 3, 11, 3, 23, 3...`
where you can see prime numbers.

#Task:
Write functions:
```
1: an(n) with parameter n: returns the first n terms of the series a(n) (not tested)

2: gn(n) with parameter n: returns the first n terms of the series g(n) (not tested)

3: countOnes(n) with parameter n: returns the number of 1 in g(n) 
    (don't forget to add a `1` at the head) # (tested)
    
4: p(n) with parameter n: returns an array of n unique prime numbers (not tested)

5: maxp(n) with parameter n: returns the biggest prime number of the sequence pn(n) # (tested)

6: anOver(n) with parameter n: returns an array (n terms) of the a(i)/i for every i such g(i) != 1 (not tested but interesting result)

7: anOverAverage(n) with parameter n: returns as an *integer* the average of anOver(n)  (tested)
```

#Note:
You can write directly functions `3:`, `5:` and `7:`. There is no need to write functions `1:`, `2:`, `4:` `6:`
except out of pure curiosity.

Difficulty: EASY
Tags: Fundamentals

Mathematics

Starter code:
def count_ones(n):
	

Solutions:
from fractions import gcd

def seq():
	(i, a, g) = (1, 7, 1)
	while 1:
		yield (i, a, g)
		i += 1
		g = gcd(i, a)
		a += g

def count_ones(n):
	return sum((g == 1 for (_, (i, a, g)) in zip(range(n), seq())))

def p(n):
	seen = set()
	for (i, a, g) in seq():
		if not n:
			break
		if g > 1 and g not in seen:
			n -= 1
			seen.add(g)
			yield g

def max_pn(n):
	return max(p(n))

def an_over(n):
	for (i, a, g) in seq():
		if not n:
			break
		if g > 1:
			n -= 1
			yield (a / i)

def an_over_average(n):
	return sum(an_over(n)) / n


from fractions import gcd
from sys import maxsize

def an(length):
	current = 7
	for index in range(length):
		yield current
		current += gcd(index + 2, current)

def gn(length):
	previous = False
	for current in an(length):
		if previous:
			yield (current - previous)
		else:
			yield 1
		previous = current

def pn(length):
	seen = set()
	count = 0
	for current in gn(maxsize):
		if current != 1 and current not in seen:
			seen.add(current)
			count += 1
			yield current
		if count == length:
			break

def max_pn(length):
	return max(pn(length))

def an_over(length):
	count = 0
	for (i, (a, g)) in enumerate(zip(an(maxsize), gn(maxsize))):
		if g != 1:
			count += 1
			yield (a / (i + 1))
		if count == length:
			break

def an_over_average(length):
	return sum(an_over(length)) / length

def count_ones(length):
	count = 0
	for x in gn(length):
		if x == 1:
			count += 1
	return count


def count_ones(n):
	(a, ones) = (7, 1)
	for i in range(2, n + 1):
		b = a + gcd(i, a)
		if b == a + 1:
			ones += 1
		a = b
	return ones

def max_pn(n):
	(a, p, i) = (7, {1}, 1)
	while len(p) < n + 1:
		i += 1
		b = a + gcd(i, a)
		p.add(b - a)
		a = b
	return max(p)

def an_over_average(n):
	return 3

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a


from math import gcd
(a, res1, res2, memo) = (6, [0], [1], {1})
for i in range(1, 1000000):
	x = a + gcd(i, a)
	(a, g) = (x, x - a)
	res1.append(res1[-1] + (g == 1))
	if g not in memo:
		res2.append(max(res2[-1], g))
		memo.add(g)
count_ones = res1.__getitem__
max_pn = res2.__getitem__
an_over_average = lambda _: 3


from math import gcd
LIMIT = 10 ** 6
an = [7]
for n in range(2, LIMIT + 1):
	an.append(an[-1] + gcd(an[-1], n))
gn = [1] + [y - x for (x, y) in zip(an, an[1:])]
primes = []
for x in gn:
	if x > 1 and x not in primes:
		primes.append(x)

def count_ones(n):
	return gn[:n].count(1)

def max_pn(n):
	return max(primes[:n])

def an_over_average(n):
	return 3


from fractions import gcd

def gn(n):
	prev = 7
	i = 2
	res = [1]
	while i <= n:
		nou = prev + gcd(prev, i)
		res.append(nou - prev)
		prev = nou
		i += 1
	return res

def count_ones(n):
	a = [x for x in gn(n) if x == 1]
	return len(list(a))

def pn(n):
	prev = 7
	i = 2
	res = []
	cnt = 0
	while cnt < n:
		nou = prev + gcd(prev, i)
		d = nou - prev
		if d != 1 and d not in res:
			res.append(d)
			cnt += 1
		prev = nou
		i += 1
	return res

def max_pn(n):
	return max(pn(n))

def an_overn(n):
	prev = 7
	i = 2
	res = []
	cnt = 0
	while cnt < n:
		nou = prev + gcd(prev, i)
		d = nou - prev
		if d != 1:
			res.append(nou / i)
			cnt += 1
		prev = nou
		i += 1
	return res

def an_over_average(n):
	a = an_overn(n)
	return int(sum(a) / len(a))


from math import gcd
seq = [7]
diff = [1]
for i in range(2, 100001):
	seq.append(seq[-1] + gcd(i, seq[-1]))
	diff.append(seq[-1] - seq[-2])
unique = [5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, 60647, 121403, 242807, 19, 37, 17, 199, 29, 486041, 421, 972533, 577]
count_ones = lambda n: diff[:n].count(1)
max_pn = lambda n: max(unique[:n])
an_over_average = lambda n: 3 * n / n


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)

def count_ones(n):
	a = [6, 7]
	for i in range(2, n + 1):
		a.append(a[i - 1] + gcd(i, a[i - 1]))
	return sum([a[i + 1] - a[i] == 1 for i in range(n)])

def max_pn(n):
	(a, p, i) = (7, {1}, 1)
	while len(p) < n + 1:
		i += 1
		b = a + gcd(i, a)
		p.add(b - a)
		a = b
	return max(p)

def an_over_average(n):
	return 3


from math import gcd
a = [7]
g = [1]
p = []
pn = []
ones = [1]
anover = []
for i in range(2, 1000000):
	c = gcd(a[-1], i)
	g.append(c)
	a.append(a[-1] + c)
	if c != 1:
		p.append(c)
		if c not in pn:
			pn.append(c)
		ones.append(ones[-1])
		anover.append(a[-1] / i)
	else:
		ones.append(ones[-1] + 1)

def count_ones(n):
	return ones[n - 1]

def max_pn(n):
	return max(pn[:n])

def an_over_average(n):
	return 3