# Spodnja funkcija izracuna, na koliko nacinov lahko stevilo zapisemo kot vsoto samih
# razlicnih kvadratov.
# Glavna ideja je, da sta za vsak kvadrat dve možnosti: ali je del vsote, ali ni.
# Argument zacetni_koren pove funckiji, s katerim kvadratom (zacetni_koren ** 2) naj
# poskusi zapisati vsoto. Ko funkcijo prvic poklicemo, je zacetni_koren privzeto 1.
# Funkcija bo zato locila dva primera: ali se v vsoti pojavi 1, ali ne.
# Za vsakega od obeh primerov se bo rekurzivno poklicala, da ugotovi, koliko moznih
# vsot pride od vsakega primera. V nobenem od podprimerov ne bo vec poskusala uporabiti 1,
# ker je bila ta moznost ravnokrat izcrpana.
def vsota_kvadratov(n, zacetni_koren = 1):
    # Ce je zacetni_koren ** 2 > n, ta kvadrat ne more biti del vsote. Vrnemo 0.
    # Do takega rekurzivnega klica pride, ko postane vsota vecja od stevila.
    if n - (zacetni_koren ** 2) < 0:
        return 0
    if n == (zacetni_koren ** 2):
        return 1
    # m = zacetni_koren**2 poskusamo uporabiti v vsoti stevila n.
    # Ce je m del vsote, nas zanima, na koliko nacinov lahko kot vsoto vecjih kvadratov
    # zapisemo stevilo n - m. Ce ni, pa nas zanima isto za stevilo n.
    # Uporabiti smemo le vecje kvadrate. Vse manjse kvadrate smo ze izcrpali do trenutnega
    # klica funkcije.
    return vsota_kvadratov(n - zacetni_koren ** 2, zacetni_koren + 1) + (
        vsota_kvadratov(n, zacetni_koren + 1))

# Ce bi kvadrate lahko uporabili poljubno mnogokrat, bi postala naloga bistveno tezja.

# Koliko je takih stevil m, spodnja_meja <= n < zgornja_meja, ki se jih da kot vsoto
# zapisati n n razlicnih nacinov.
def n_nacinov(spodnja_meja, zgornja_meja, n):
    stevec = 0
    seznam_stevil = []
    for i in range(spodnja_meja - 1, zgornja_meja):
        if vsota_kvadratov(i) == n:
            stevec += 1
            seznam_stevil.append(i)
    return stevec, seznam_stevil

seznam_moznih_stevil = n_nacinov(1, 501, 50)
print(seznam_moznih_stevil)

#Dobimo 4 stevila. Eno od njih je pravo.