6 times a number gives a 6-prefixed similar number

six_times_number.py

"""
Ξερουμε απο την εκφώνηση οτι ο ζητούμενος αριθμός θα εχει τελευταιο ψηφίο το 6. Εστω x ο αριθμός που σχηματιζεται
απο τα ψηφία πριν το τελευταίο ψηφίο 6. Π.χ. για το πάραδειγμα με τον αρχικο αριθμό
4356 το x θα ειναι το 435. Αρα ο αρχικός μας αριθμός μπορεί να γραφει αλγεβρικα ως 10 * x + 6. Εστω επίσης n 
τα ψηφία του αριθμού x (αρα n+1 ειναι τα ψηφία του αρχικού αριθμού). Τοτε αν μεταφέρουμε το 6 στην πιο αριστερη 
(πρώτη) θέση θα προκυψει ο αριθμός 6 * 10^n + x Π.χ. για τον αρχικό αριθμό 4356, το x=435 εχει 3 ψηφία και με τον
μετασχηματισμό έχουμε τον 6435 = 6 * 1000 + 435 = 6 * 10^3 + 435

Για να ειναι ο μετασχηματισμένος αριθμός εξαπλάσίος του αρχικου θα πρέπει: 6 * (10 * x + 6) = 6 * 10^n + x και άρα:

59 * x = 6 * 10^n - 36  (α)

Άρα το 6 * 10^n - 36 θα πρέπει να διαιρείται ακριβώς με το 59 (δηλ. υπόλοιπο 0), και το πηλίκο ειναι ο αριθμός x
που πρεπει να έχει n ψηφία. Αρα μπορούμε να κάνουμε δοκιμές με διαφορετικούς αριθμούς ψηφίων μεχρι να βρουμε κάποιο
ν. Αν βρούμε το n, υπολογίζουμε το x απο την (α) και τον αρχικό αριθμό.

Η συνάρτηση check σε Python τσεκάρει για ενα δεδομένο αριθμό ψηφίων. Η συνάρτηση solutions επιστρέφει σε λίστα
τις λύσεις μέχρι ενα μεγιστο αιθμό ψηφίων (100 by default).

Αν τρεξουμε την solutions με το default μεγιστο αριθμό ψηφίων (100) παιρνουμε 1 λύση:

1016949152542372881355932203389830508474576271186440677966

που εχει 58 ψηφία

Τρεχοντας το solutions(4000) (δηλ. μεχρι 4000 ψηφία) βρισκουμε συνολικα 68 λύσεις, η μεγαλύτερη με 3944 ψηφία!

"""


def check(n):
    """Τσεκάρει αν υπάρχει αριθμός x με n ψηφία που ικανοποιεί την σχέση (α). 
    Επιστρέφει -1 αν δεν υπάρχει τέτοιος, ή τον αρχικό αριθμό που ψάχνουμε"""
    y = 6* 10**n - 36
    x, k = divmod(y, 59)
    return x*10 + 6 if k == 0 and len(str(x)) == n else -1



def solutions(max_digit=100):
    """Επιστρέφει σε λίστα ολες τις λύσεις (αρχικό αριθμό) με αριθμό ψηφίων μέχρι και max_digit"""
    return [check(s) for s in range(max_digit) if check(s) != -1]