Consider the following well known rules:

- A number is divisible by 3 if the sum of its digits is divisible by 3. Let's call '3' a "1-sum" prime
- For 37, we take numbers in groups of threes from the right and check if the sum of these groups is divisible by 37. 
  Example: 37 * 123456787 = 4567901119 => 4 + 567 + 901 + 119 = 1591 = 37 * 43. Let's call this a "3-sum" prime because we use groups of 3.
- For 41, we take numbers in groups of fives from the right and check if the sum of these groups is divisible by 41. This is a "5-sum" prime.
- Other examples: 239 is a "7-sum" prime (groups of 7), while 199 is a "99-sum" prime (groups of 99).

Let's look at another type of prime:
- For 11, we need to add all digits by alternating their signs from the right. 
  Example: 11 * 123456 = 1358016 => 6-1+0-8+5-3+1 = 0, which is divible by 11. Let's call this a "1-altsum" prime
- For 7, we need to group the digits into threes from the right and add all groups by alternating their signs.
  Example: 7 * 1234567891234 = 8641975238638 => 638 - 238 + 975 - 641 + 8 = 742/7 = 106. 
- 7 is a "3-altsum" prime because we use groups of threes. 47 is a "23-altsum" (groups of 23), while 73 is a "4-altsum" prime (groups of 4).


You will be given a prime number `p` and your task is to find the smallest positive integer `n` such that `p’s` divisibility testing is `n-sum` or `n-altsum`.

For example:
```
solve(3) = "1-sum"
solve(7) = "3-altsum"
```
Primes will not exceed `50,000,000`. More examples in test cases. 

You can get some insight from [Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem). 

Good luck!

Source: codewars | Difficulty: EASY
Tags: Fundamentals

Starter code: def solve(p):
	

Solutions:
import math

def divisors(n):
	divs = [1]
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			divs.extend([i, n // i])
	divs.extend([n])
	return list(set(divs))

def solve(p):
	for d in sorted(divisors(p - 1)):
		if pow(10, d, p) == 1:
			return '{}-sum'.format(d)
			break
		elif pow(10, d, p) == p - 1:
			return '{}-altsum'.format(d)
			break


import collections
import itertools

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

def prod(iterable):
	result = 1
	for i in iterable:
		result *= i
	return result

def get_divisors(n):
	pf = prime_factors(n)
	pf_with_multiplicity = collections.Counter(pf)
	powers = [[factor ** i for i in range(count + 1)] for (factor, count) in pf_with_multiplicity.items()]
	for prime_power_combo in itertools.product(*powers):
		yield prod(prime_power_combo)

def rem(n, p):
	v = 1
	for i in range(0, n // 1000):
		v = v * 10 ** 1000
		v = v % p
	v = v * 10 ** (n % 1000)
	v = v % p
	return v

def solve(p):
	nl = list(get_divisors(p - 1))
	nl = [int(x) for x in nl]
	nl = sorted(nl)
	for n in nl:
		if rem(n, p) == 1:
			return str(n) + '-sum'
		if rem(n, p) == p - 1:
			return str(n) + '-altsum'


def solve(p):
	result = 0
	for i in range(1, int(p ** 0.5) + 1):
		if (p - 1) % i:
			continue
		if pow(10, i, p) == 1:
			result = i
			break
		j = (p - 1) // i
		if pow(10, j, p) == 1:
			result = j
	if pow(10, result // 2, p) == p - 1:
		return f'{result // 2}-altsum'
	else:
		return f'{result}-sum'


def solve(p):
	n = p - 1
	for f in factors(n):
		m = n // f
		if pow(10, m, p) == 1:
			n = m
	return '%d-altsum' % (n // 2) if n % 2 == 0 else '%d-sum' % n

def factors(n):
	m = 2
	while m * m <= n:
		while n % m == 0:
			yield m
			n //= m
		m += 1 if m == 2 else 2
	if n > 1:
		yield n


def solve(p):
	n = p - 1
	while n % 2 == 0 and pow(10, n, p) == 1:
		n //= 2
	s = pow(10, n, p)
	for p2 in factors_gen(n):
		if pow(10, n // p2, p) == s:
			n //= p2
	return ('%d-sum' if s == 1 else '%d-altsum') % n

def factors_gen(n):
	while n % 2 == 0:
		yield 2
		n //= 2
	k = 3
	while k * k <= n:
		while n % k == 0:
			yield k
			n //= k
		k += 2
	if n > 1:
		yield n


def solve(p):
	d2 = -1
	for d in range(1, int(p ** 0.5) + 1):
		if (p - 1) % d == 0:
			k = pow(10, d, p)
			if k == 1:
				return f'{d}-sum'
			elif k == p - 1:
				return f'{d}-altsum'
			t = (p - 1) // d
			k = pow(10, t, p)
			if k == 1 or k == p - 1:
				d2 = t
	return f'{d2}-sum' if pow(10, d2, p) == 1 else f'{d2}-altsum'


from math import floor, sqrt

def solve(p):

	def powmod(x, n):
		(res, cur) = (1, x)
		while n:
			if n & 1 == 1:
				res = res * cur % p
			cur = cur * cur % p
			n = n >> 1
		return res

	def invert(x):
		return powmod(x, p - 2)
	BLOCK = 1000
	base = 10
	baby = dict()
	bcur = base % p
	for i in range(1, BLOCK):
		if bcur not in baby:
			baby[bcur] = i
		else:
			break
		bcur = bcur * base % p
	step = invert(powmod(base, BLOCK))
	pcur = 1
	for j in range(0, p, BLOCK):
		ans = []

		def try_use(num, typ):
			if num in baby:
				totnum = j + baby[num]
				if totnum > 0:
					ans.append((totnum, typ))
			if num == 1 and j > 0:
				ans.append((j, typ))
		try_use(pcur, 'sum')
		try_use((p - 1) * pcur % p, 'altsum')
		if ans:
			return '%d-%s' % min(ans)
		pcur = pcur * step % p


def solve(p):
	(i, ans) = (1, 0)
	while i * i <= p - 1:
		if (p - 1) % i == 0:
			j = (p - 1) // i
			if pow(10, i, p) == 1:
				ans = i
				break
			if pow(10, j, p) == 1:
				ans = j
		i += 1
	if pow(10, ans // 2, p) == p - 1:
		ans = str(ans // 2) + '-altsum'
	else:
		ans = str(ans) + '-sum'
	return ans