Every natural number, ```n```, may have a prime factorization like:



We define the arithmetic derivative of ```n```, ```n'``` the value of the expression:



Let's do the calculation for ```n = 231525```.
```
231525 = 3³5²7³ 
n' = (3*3²)*5²7³ + 3³*(2*5)*7³ + 3³*5²*(3*7²) = 231525 + 92610 + 99225 = 423360
```
We may make a chain of arithmetic derivatives, starting from a number we apply to the result the transformation and so on until we get the result ```1```.
```
n ---> n'  ---> (n')' ---> ((n')')' ---> ..... ---> ((...(n')...)')'
```
Let's do it starting with our number, ```n = 231525``` and making a chain of 5 terms:
```
231525 ---> 423360 ---> 1899072 ---> 7879680 ---> 51895296
```
We need a function ```chain_arith_deriv()``` that receives two arguments: ```start``` and ```k```, amount of terms of the chain.

The function should output the chain in an array format:
```
chain_arith_deriv(start, k) ---> [start, term1, term2, .....term(k-1)] # a total of k-terms
```
For the case presented above:
```python
chain_arith_deriv(231525, 5) == [231525, 423360, 1899072, 7879680, 51895296]
```
The function has to reject prime numbers giving an alerting message
```python
chain_arith_deriv(997, 5) == "997 is a prime number"
```
Features of the tests:
```
Number of Random Tests: 50
1000 ≤ start ≤ 99000000
3 ≤ k ≤ 15
```
Enjoy it and do your best!

Source: codewars | Difficulty: EASY
Tags: Fundamentals

Mathematics

Complete search

Starter code: def chain_arith_deriv(n, k):
	

Solutions:
def chain_arith_deriv(n, k):
	if len(prime_factors(n)) < 2:
		return '{} is a prime number'.format(n)
	chain = [n]
	while k > 1:
		(k, n) = (k - 1, arith_deriv(n))
		chain.append(n)
	return chain

def arith_deriv(n):
	factors = prime_factors(n)
	return sum((n * factors.count(factor) // factor for factor in set(factors))) or 1

def prime_factors(n):
	if n < 2:
		return []
	factors = []
	for k in (2, 3):
		while n % k == 0:
			n //= k
			factors.append(k)
	k = 5
	step = 2
	while k * k <= n:
		if n % k:
			k += step
			step = 6 - step
		else:
			n //= k
			factors.append(k)
	if n > 1:
		factors.append(n)
	return factors


from collections import Counter

def factors(n):
	step = lambda x: 1 + 4 * x - (x - x % 2)
	(d, q, qmax) = (1, 2 + n % 2, int(n ** 0.5))
	while q <= qmax and n % q:
		q = step(d)
		d += 1
	return q <= qmax and [q] + factors(n // q) or [n]

def chain_arith_deriv(start, k):
	(n, chain) = (start, [])
	for _ in range(k):
		chain.append(n)
		fac = Counter(factors(n))
		n = sum((n // p * k for (p, k) in fac.items()))
	return chain if chain[1] > 1 else '%d is a prime number' % start


def chain_arith_deriv(n, k):
	r = [n]
	while len(r) < k:
		d = decompose(r[-1])
		if n in d and len(r) == 1:
			return str(n) + ' is a prime number'
		r.append(sum((r[-1] / i * d[i] for i in d)))
	return r

def decompose(n):
	(i, f) = (2, {})
	while i * i <= n:
		while n % i == 0:
			f[i] = f.get(i, 0) + 1
			n //= i
		i += 1
	if n > 1:
		f[n] = 1
	return f if f else {1: 1}


def chain_arith_deriv(start, k):
	res = [start]
	for i in range(k - 1):
		s = 0
		r = factorize(start)
		if i == 0 and r == {start: 1}:
			return str(start) + ' is a prime number'
		try:
			for n in r:
				p = 1
				for n2 in r:
					p *= r[n2] * n2 ** (r[n2] - 1) if n2 == n else n2 ** r[n2]
				s += p
			start = s
			res.append(s)
		except:
			res.append(1)
	return res

def factorize(num):
	if num < 4:
		return [num]
	r = {}
	d = 2
	while d < num ** 0.5 + 1:
		while not num % d:
			r[d] = r[d] + 1 if d in r else 1
			num /= d
		d += 1 if d == 2 else 2
	if num != 1:
		r[num] = 1
	return r


def _prime_factors(n):
	factors = {}
	i = 2
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			if i in factors.keys():
				factors[i] += 1
			else:
				factors[i] = 1
	if n > 1:
		if n in factors.keys():
			factors[n] += 1
		else:
			factors[n] = 1
	return factors

def chain_arith_deriv(start, m, chain=None):
	factors = _prime_factors(start)
	if len(factors) == 1 and chain is None:
		return '{} is a prime number'.format(start)
	if chain is None:
		chain = []
	chain.append(start)
	if m == 1:
		return chain
	elif start == 1:
		next_num = 1
	else:
		next_num = 0
		for (p, k) in factors.items():
			next_num += k / p * start
	return chain_arith_deriv(round(next_num), m - 1, chain=chain)


from sys import version_info
if version_info.major >= 3:
	long = int
from collections import Counter
from math import floor, sqrt
from random import randint

def is_prime(number):
	if number > 1:
		for time in range(3):
			randomNumber = randint(2, number) - 1
			if pow(randomNumber, number - 1, number) != 1:
				return False
		return True
	else:
		return False

def fac(n):
	step = lambda x: 1 + (x << 2) - (x >> 1 << 1)
	maxq = int(floor(sqrt(n)))
	d = 1
	q = n % 2 == 0 and 2 or 3
	while q <= maxq and n % q != 0:
		q = step(d)
		d += 1
	return q <= maxq and [q] + fac(n // q) or [n]

def f_arith_deriv_(n):
	primeCount = Counter(fac(n))
	n_ = 0
	for (k, v) in list(primeCount.items()):
		n_ += v * n // k
	return n_

def chain_arith_deriv(n, k):
	if is_prime(n):
		return str(n) + ' is a prime number'
	chain = [n]
	while True:
		next_ = f_arith_deriv_(n)
		chain.append(next_)
		if len(chain) == k:
			break
		n = next_
	return chain


from collections import defaultdict

def derivate(x):
	divisors = defaultdict(int)
	n = x
	i = 2
	while i * i <= x:
		while x % i == 0:
			divisors[i] += 1
			x /= i
		i += 1
	if x > 1:
		divisors[x] += 1
	if len(divisors) < 2:
		return 1
	return sum((k * n / p for (p, k) in divisors.items()))

def chain_arith_deriv(start, k):
	result = [start]
	for i in range(k - 1):
		result.append(derivate(result[-1]))
		if len(result) == 2 and result[-1] == 1:
			return '%d is a prime number' % start
	return result


from fractions import Fraction
from collections import Counter

def isPrime(n):
	if n < 3 or not n % 2:
		return n == 2
	return all((n % x for x in range(3, int(n ** 0.5) + 1, 2)))

def prime_factors(n):
	i = 2
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			yield i
	if n > 1:
		yield n

def rec(current, k):
	if not k:
		return []
	if current == 1:
		return [1] * k
	return [current] + rec(current * sum((Fraction(v, k) for (k, v) in Counter(prime_factors(current)).items())), k - 1)

def chain_arith_deriv(start, k):
	if isPrime(start):
		return '{} is a prime number'.format(start)
	return rec(start, k)


def chain_arith_deriv(start, k):
	if is_prime(start):
		return '{} is a prime number'.format(start)
	(chain, n) = ([], float(start))
	for i in range(k):
		chain.append(n)
		n = sum((n * v / k for (k, v) in list(prime_factors_dict(n).items())))
		if n == 1:
			break
	return chain + [1] * (k - len(chain))

def is_prime(num):
	return num == 2 or (num > 2 and all((num % i for i in range(2, int(num ** 0.5) + 1))))

def prime_factors_dict(n):
	(d, exp) = ({}, 0)
	while n % 2 == 0:
		exp += 1
		n //= 2
	if exp:
		d[2] = exp
	for i in range(3, int(n ** 0.5) + 1):
		exp = 0
		while n % i == 0:
			exp += 1
			n //= i
		if exp:
			d[i] = exp
	if n > 1:
		d[n] = 1
	return d