WisFaq!

Samengestelde getallen bestaande uit priemfactoren 243

Hoe spoor je samengestelde getallen op van slechts 2 cijfers en bestaande uit alleen priemfactoren $\Leftarrow$ 97? V.b.: 111 112 = 2³.17.19.43 en 11 111 116 = 2².23².59.89

Steven Verhezen
4-3-2013

Antwoord

Met bijgaand Python programma kun je ze berekenen:

primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
maxnumber=pow(10,4)

def test(n):
    if n<100 and n in primes:
        return False #we willen alleen samengestelde getallen
    for f in primes:
        while n%f==0 : n/=f
        if n==1:break
    if n==1: return True
    return False

def recurse(n,digits,useddigits):
    global count
    if len(useddigits)==2 and test(n):
        res.append(n)
        count+=1
   
    n=10*n
    for d in digits:
        t=set(useddigits)
        t.add(d);
        if n+d < maxnumber: recurse(n+d,digits,t)
count=0
res=[]
for i in xrange(1,10):
    for j in xrange(0,10):
        if i<>j:
            digits=[i,j]
            s=set()
            s.add(i);
            recurse(i,digits,s)
print count
print sorted(res)

Door de variabele maxnumber aan te passen kun je ook grotere getallen vinden.

Als je geen Python op je computer hebt kun je het downloaden en installeren. Het is geschreven in Python 2.7.
(Python is freeware).

hk
10-3-2013