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!

Difficulty: introductory

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):
    """See codewars.com kata Divisible by primes."""
    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