Összeadás és oszthatóság

Algoritmusok

Sziasztok,

a ProjectEuler egyik problémáját próbálom megoldani és ehhez szeretnék egy kis segítséget kérni. Az érdekelne, hogy van-e olyan összefüggés ami megmondja, hogy ha adott n és m természetes szám {p_1, p_1', p_1''...} és {p_2, p_2', p_2'' ...} prímtényezőkkel, akkor n + m = c-nek hány prímtényezője van? Az osztók számára lenne igazából szükségem, de az a prímtényezőkből már kijön.

A legközelebbi eredmény, ami segíthet az talán ennek a szekciónak a legvégén található, de egyenlőre nem látom, hogy ebből hogyan következik a megoldás csak két term. számra.

Előre is köszi minden segítséget/olvasnivalót.

  • 5241 megtekintés

( mkristof | 2009. 06. 24., sze – 22:38 )

up?

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

( mzn v | 2009. 06. 24., sze – 23:00 )

Így hirtelen, összeszámolod a közös prímosztókat multiplicitással, kiemeled, a maradékot meg kiszámolod, és csinálsz rá egy prímfelbontást.

A = 2*2*2*3*5*5*7
B = 2*2*3*3*11

C = (2*2*3)*(2*5*5*7+3*11) = (2*2*3)*383

Ez így nem jó? Vagy nagyon nagyok a számok?

Elsőre nem látom az elvet, de még emésztem. A példáddal meg valami baj lehet, mert nekem azt mondja a számológépem, hogy:

>>> A
8400
>>> B
396
>>> C
8796
>>> (2*2*3)*383
4596

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

( tomaza | 2009. 06. 24., sze – 23:21 )

1. hogy jön ki a prímtényezők számából az osztók száma? (kitevő is kell hozzá, vagy ha úgy érted lehet p1'=p1'' akkor meg tudni kellene hogy egyenlőek-e: gondoltam egy számra, 3 prímtényezője van, hány osztója? 8-nak és 30-nak nem ugyanannyi, ill. 8-nak és 2-nek sem)
2. rossz úton jársz valszeg

A 2,-re még nem tudom a választ, de az elsőre tudok felelni.

Egy n természetes szám kanonikus alakja a megfelelő kitevőre emelt prímtényezők szorzata. (A megfelelő kitevő = ahányszor előfordul a felbontás során.) Például a 40 kanonikus alakja a 2^3 x 5.

A kanonikus alakból a fenti link - és más, nálam okosabb emberek szerint - úgy következik az osztók száma, hogy fogod a prímtényezők kitevőit, mindegyikhez hozzáadsz egyet és ezeket az összegeket összeszorzod. Azaz pl a 40 esetén, d(40) = (3 + 1)(1 + 1) = 8, és láss csodát a 40 osztói: {1,2,4,5,8,10,20,40}.

Ha nem pontos, akkor bocsánat, bölcsész vagyok amúgy. :)

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

Az 1-re a bizonyítás is egyszerű, hiszen tetszőleges osztót megkaphatsz úgy, hogy a prímtényezők közül összeszorzol valahányat, vagyis csak azt kell kiszámolni, hogy a generálandó osztó prímtényezős felbontásában hányféleképpen állíthatod be az egyes kitevőket, ami pedig pont a (kitevő+1)-ek szorzata, lévén minden kitevő nulladik hatványon is állhat.

A kiegészítéssel viszont jogos a kérdés és pontatlan az én kérdésem.
n + m = c-ről vagy azt szeretném tudni, hogy hány osztója van, csupán n és m osztói száma alapján, vagy pedig azt, hogy mik a prímtényezői, n és m prímtényezői alapján.

Így pontos?

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

így okés, de a 2-es pont még mindig áll :)
-persze az osztók megintcsak nem működnek: 2 osztója van 2,3,5-nek, 2+3 -nak 2, 3+5-nek több
-a prímtényezők alapján most csak érzésre mondom hogy túl bonyolult az euler laphoz, de már nagyon régen néztem, és és lehet hogy az matek emlékeim koptak :)

( cus | 2009. 06. 24., sze – 23:58 )

Nem teljesen értem, hogy ezt a feladatot akkor most egy polinóm idejű algoritmussal akarod megoldani?

Mert szerintem c szám prímtényezős felbontását nem fogod polinóm időben előállítani, szóval valahogy máshogy kéne próbálkozni...

Nem, nem, csak arra lettem volna kíváncsi, hogy van-e olyan összefüggés, A = B alakú szabály, ami megmondja c prímtényezőit, ha már n-ét és m-ét ismerjük. (Kb. úgy mint ahogy az osztók száma kiderül a kanonikus alakból) De a válaszodból úgy tűnik, hogy ilyen összefüggés nincs, akkor próbálkozok máshogy. :)

A feladat egyébként az, hogy meg kéne találni az első olyan háromszögszámot amelynek ötszáznál több osztója van. Biztos nem egy nagy feladat, nekem pont megfelelő kihívás, és gondoltam most először nem brutforce-al mennék neki, hanem megpróbálném okosba'...

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

Ja bocsi, most veszem észre, hogy ezt már megtaláltam. (Nem, nem tanultam, bölcsész vagyok mint mondtam.) Háromszögszámokat tudok gyártani, elég sokáig, az osztókkal vagyok bajban.


l = map(lambda x: sum(range(1,x)), range(2,12))

Azért gondoltam, hogy egy ilyen m + n = c megoldás lenne a jó, mert akkor nem kéne előre legenerálni a listát, hanem ahogy haladnék előre egytúl úgy mindig az előzőből + a sorszámból meglenne az aktuális háromszögszám és az osztók száma is.
-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

"Nem, nem, csak arra lettem volna kíváncsi, hogy van-e olyan összefüggés, A = B alakú szabály, ami megmondja c prímtényezőit, ha már n-ét és m-ét ismerjük. "
A fenti példám alapján (ahol fáradt voltam, érthetőbb lett volna legnagyobb közös osztót írni), ha a 11 helyett 19-et veszel, akkor a 383-ból 407 lesz, ami pedig osztható 11-gyel. Vagyis szinte biztos, hogy nincs olyan formula, ami megadná, mert a 11 és a 19 prímség szempontjából ugyanolyan.

Szia!

Valószínűleg nincs olyan általános összefüggés amit keresel!

Például így van akkor, ha igaz a Goldbach sejtés. Akkor tetszőleges páros szám (ez rengeteg féle különböző osztószámot jelent), felírható két prímszám összegeként (amiknek csak 1 és önmaguk az osztói).

Azaz pl. ismered hogy A prím meg B prím és A>2 és B>2, akkor A+B osztóira ebből szinte semmiféle következtetést nem tehetsz. (Na jó 2-vel osztható lesz, de ennyi...)

Na jó, nem is kell hogy igaz legyen a Goldbach sejtés... Információelméletileg elég annyit belátni, hogy többféle osztószám kimenet lehetséges két prímszám összeadásából (ami mindig egyféle osztószám bemenetet jelent), és ez könnyen látható.

Tehát a kettő között (osztószám bemenet, és kimenet) nem létezhet függvénykapcsolat.

(szerk. persze ettől a feladat megoldható, de járulékos információkat tuti biztos igényel)