Barátságos számok

Volt egyszer egy király, aki nagy matematikusnak képzelte magát. Egyszer azt mondta az egyik rabnak: "Adj fel nekem egy feladatot, s én megoldom. Amíg nem ismerem a megoldást, addig szabadon jöhetsz-mehetsz, de amint tudom rá a választ, a fejed elválik a nyakadtól!" A fogoly nagyon ravasz fejtörőt eszelt ki:

A 220 és a 284 úgynevezett barátságos számpár. A 220 valódi osztóinak összege 284-et ad:

1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284,

a 284 valódi osztónak összege pedig 220-szal egyenlő:

1 + 2 + 4 + 71 + 142 = 220.

A királynak az értékben ezek után következő két barátságos számot kellett volna meghatároznia. A történet szerint a rab kiszabadult, és békés öregkorban halt meg, mert a király sohasem oldotta meg a feladatot.

Barátságos számpárok előállítására több módszer is van. Az egyik a következő. Legyen

a = 3 • 2^x - 1

b = 3 • 2^x-1 - 1

c = 9 • 2^2x-1 - 1

Ha x nagyobb 1-nél, és a, b, c mindegyike prímszám, akkor 2^xab és a 2^xc barátságos számpárt alkot. Ha például x = 4, akkor a = 47, b = 23 és c = 1151. Mindhárom érték prímszám.

Ebből

2⁴ • 47 • 23=17 296 (2^xab)

és

2⁴ • 1151 = 18 416 (2^xc)

A játék algoritmusának mondatszerű leírása:

Program baratsagosszamok:

Ki: Barátságos számok

Ciklusvátozó(a) = 1-től 7000-ig

s = 0

Ciklusváltozó(d) = 1-től a/2-ig

Ha a/d == INT(a/d) akkor

    s = s + d

Elágazás vége

Ciklus vége

Ha s>a akkor

b = s

t = 0

Ciklusváltozó(f) = 1-től b/2-ig

Ha b/f == INT(b/f) akkor

t = t + f

Elágazás vége

Ciklus vége

Ha t=a akkor

Ki: a, b

Elágazás vége

Elágazás vége

Ciklus vége

Program vége