Pandigital number

Pandigital number

Avtor: Nina Jug

Besedilo problema

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
What is the largest n-digit pandigital prime that exists?

Prevedeno besedilo
N-mestno število je pandigital, če uporabi vse cifre od 1 do n samo enkrat. Na primer, 2143 je 4-mestno pandigital število, ki je hkrati praštevilo.
Katero je največje n-mestno pandigital praštevilo, ki obstaja?

Opis ideje

- očitno je, da bo rešitev manjša kot 987654321, saj je to število največje pandigital število
- bolj bo smiselno, da bomo preverjali števila od največjega navzdol, saj bomo tako prihranili kar nekaj časa, kajti iščemo največje pandigital število
- ko razmišljamo naprej, pridemo do spoznanja, da 8 in 9 mestno število nikoli ne bo pandigital in hkrati praštevilo, ker je vsota števil od 1 do 8 oz. od 1 do 9 deljiva s 3.
1+2+3+4+5+6+7+8 = 36
1+2+3+4+5+6+7+8+9 = 45
- 7 mestno število bo vredu, saj je 1+2+3+4+5+6+7 = 28
- tako smo našo zgornjo mejo postavili na 7654321
- poiskali bomo vse permutacije števil od 1 do 7 in med njimi našli največje število, ki je praštevilo

Koda programa v Python-u

import math
import itertools

def permutacije(n):
    """
Metoda izpiše vse permutacije števila n.
"""
    assert type(n) == int and n>0, 'Vnešeno število mora biti večje od 0'
    sez = []
    seznam = list(itertools.permutations(str(n)))
    for i in seznam:
        niz = ''
        for j in i:
            niz+=str(j)
        sez.append(int(niz))
    return sez

def jePrastevilo(n):
    """
Metoda, ki preveri, ali je hranjeno število praštevilo (vrne True), ali ni (False)
"""
    assert type(n) == int and n>0, 'Vnešeno število mora biti večje od 0'
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def PandigitalPrimeNumber():
    """
Metoda izpiše največje 'pandigital' praštevilo.
"""
    perm = permutacije(1234567)
    seznam = []
    for i in perm:
        if jePrastevilo(i)==True:
            seznam.append(i)
    return max(seznam)

pandigital number

Naprej na komentar kode

Komentar kode

Najprej sestavimo metodo permutacije, ki nam bo za neko število izpisala vse možne permutacije tega števila. Ustvarimo prazen seznam, v katerega bomo zapisovali permutacije. Nato pa z že vgrajenim ukazom permutations, naredimo seznam vseh permutacije. Ker ta ukaz deluje samo na nizih, moramo naše število spremeniti v niz. Ker pa elementi tega seznama permutacij niso števila, temveč so števila razbita na cifre (ena od permutacij števila 123 izgleda tako ('1', '3', '2'), jih moramo na nek način pretvoriti v števila. Gremo s for zanko čez seznam permutacij. V zanki ustvarimo prazen niz, v katerega bomo dodajali cifre. Znotraj naše zanke naredimo še eno zanko, ki pa bo šla čez posamezno permutacijo. Niz bomo tako povečali za vsako cifro v permutaciji in na koncu to permutacijo (število) dodali v naš seznam. Seznam naj funkcija tudi vrne.

Ker mora biti naše iskano število tudi praštevilo, moramo sestaviti tudi metodo, ki preveri, ali je dano število praštevilo (v tem primeru metoda vrne True), ali ni (vrne False). Če je število, ki ga preverjamo enako 1, naj funkcija vrne False. Potem gremo z zanko čez vsa števila od 2 do korena števila, ki ga preverjamo, +1. Če je ostanek pri deljenju našega števila s številom v zanki enak 0, potem to število ni praštevilo. V nasprotnem primeru je.

Na koncu pa še sestavimo funkcijo, ki nam bo vrnila največje pandigital praštevilo. V seznam perm shranimo vse permutacije števila 1234567. Ustvarimo tudi nek prazen seznam, v katerega bomo shranjevali te permutacije, ki so hkrati praštevila. Z for zanko gremo čez seznam permutacij. Če je kateri od elementov tega seznama praštevilo, ga dodamo v naš seznam. Ko imamo seznam narejen, samo vrnemo maksimalen element tega seznama.

Nazaj na kodo

Testni primeri

Smiselno bi bilo, da stestiramo vse metode.
Za metodo permutacije bi uporabili:
- permutacija števila 1, 12 in 123 (za ta števila ni težko napisati vse permutacije)
Za metodo jePraštevilo bi uporabili:
- števila 1, 2, 22 (1 je deljivo z 1 in samo s seboj, vendar ni praštevilo, 2 je praštevilo, 22 je deljivo z 1, 2, 11, 22, zato ni praštevilo)
Zadnjo metodo pa preverimo na Project Euler-Problem41

(PPN.JPG)
Naša rešitev problema
(euler.JPG)
Rešitev problema na Euler strani

testni primeri

Filmček

0%
0%