A helyes képlet (N-4)*10(N-3) ... A képletből jól látható, hogy egy 1004 jegyű szám esetén már ugyanannyi számot tud leírni, mint a hagyományos módszer. 1005 jegynél és afelett meg már többet.
Igazad van, elnéztem, a helyes képlet valóban (N-4)*10(N-3)
Ha megengedünk tetszőleges egy számjegyű kitevőt (1<k<10), akkor nyilván 8-al kell szorozni a leírható számok számát. Látszik tehát, hogy értelmes nagyságú számokra még garantáltan így sem működik.
A helyes képlet (N-4)*10(N-3) (de ebben persze a duplikált számok nincsennek benne). A képletből jól látható, hogy egy 1004 jegyű szám esetén már ugyanannyi számot tud leírni, mint a hagyományos módszer. 1005 jegynél és afelett meg már többet.
Szerintem így ebben a formában nem elfogadható az indoklás. A 10(N-3) számítás ugyanis az olyan számok számopsságát adja meg, ahol a hatványozás jel fix helyen van, azaz mondjuk az 5. pozícióban. Az alábbi két szám jelsorozat között nem tesz különséget:
1111^2+2222 111^2+12222
Van még egy dolog ami bonyolítja a számítást: ezzel a módszerrel egy szám kétféleképpen is előállítható, ami meg a másik irányba billenti el a mérleg nyelvét.
Nem tudom mennyire releváns, de van egy olyan számításelméleti tétel, hogy nem létezik olyan algortimus amely minden adatot képes tömöríteni. Amiért ebben nem vagyok biztos az alkalmazhatóságában az azért van, mert itt vannak plusz jelek, azaz itt nem igazi tömörítésről van szó, hanem egyfajta pszeudó tömörítésről.
"A^2+B" alakú N hosszú stringből csak 10^(N-3) darab van, míg simán "A" alakú stringből 10^(N) darab van: így semmiképpen nem lehet tehát "A^2+B" alakkal megverni az eredeti "A" alakot. Hasonló okoskodással látható, hogy semmilyen 'fix minta' nem működhet.
Nekem az a sejtésem, hogy egy méret felett ugyan minden számot fel lehet írni rövidebben, mint a sima "A" alak, de ennek a bizonyítása nagyon-nagyon nehéz lehet, mivel nem lehet egyszerű konstrukciót találni. Ettől függetlenül lehet, hogy mindjárt valaki megtalálja a megfelelő konstrukciót:)
Azt hiszem 3. hatványokkal kellene operálni. Azokon elég sokat lehet spórloni, viszont még talán nem esnek túl távol egymástól. Vagy esetlg két 3. hatvány szorzataként előállítani a számokat (természetesen erre még jön egy összeg).
Hosszas gondolkodás után egy elég egyszerűen végiggondolható dolog jutott eszembe. Nézzük az a2+b alakot. Az (a+1)2-a2 = 2*a+1. Ebből következik, hogy ha n a kódolandó szám, akkor azt mindig lehet úgy a2-el közelíteni, hogy a különbség maximum a legyen (használom a minusz jelet is). Még a létező legrosszabb esetben is igaz, hogy a számjegyeinek száma n számjegyeinek (ezt jelöljük s(n)-el) a száma felfelé kerekítve, így n-t képlettel felírhatjuk legfeljebb s(n)+2+3, azaz s(n)+5 számjeggyel. Tudom, hogy ez nem egy nagy eredmény, de azért eredmény. Ezzel a módszerrel az elérhető legjobb eredmény s(n)+3 (ha olyan a-t találunk, aminek a négyzete pont dupla annyi számjegyből áll, mint a).
Persze lehet, hogy ez az irány zsákutca és a megoldás teljesen másfelöl fog érkezni. De azért talán nem árt végiggondolni, hiszen ha magasabb hatványokat is beleveszünk, akkor talán működhet.
tehát élesebb becslés kell, mert az kevés, hogy (a^b+) legalább 4-jegyet visz el, mert hát sokkal többet. legtömörebb, ha b nagy, a kicsi, jelesül 2^b alakú, ekkor elvisz log2(n) +3 jegyet. d-nek tehát legfeljebb log(n)-log2(n)-3-jegyűnek kellene lennie...
(közben máson is dolgozom, szóval zaklatott amit írok, de ezek jutnak eszembe)
tényleg adott n-hez keressünk ilyen felírást: n = a^b + d
b fut 2 -től log2(n)-ig.
a lesz hozzá floor(n1/b) (alsó egészrész), hiszen ekkor ab<n < ab+1
Az viszont igaz, hogy n "körül" (előtt) csak log(n) esélyes hatvány van.
Azt is gondolnám, hogy n várhatóan egyenletesen esik bele az [ab, ab+1] intervallumba, ami pedig méretes, mert ab*(a-1) méretű, ami az n nagyságrendje; ennek kellene legalább az első 1000-edrészébe esnie valamelyik a,b párra, hogy a d kicsi legyen.
Na de ha a log2(n) >>1000, akkor ez nagy valószínűséggel teljesül...
A feladat az, hogy, igaz-e, hogy egy bizonyos 't' természetes szám felett minden szám kevesebb karakterben felírható 'képlettel', mintha csak simán felírnánk tízes számrendszerben, ahol 'képlet'-en olyan kifejezést értünk, amelyben:
a 0-9 karakterek, a + * ^ karakterek szerepelhetnek, és a szokásos módon értelmeződnek (tízes számrendszerbeli számok közötti műveletekként.) (Eredetileg a zárójeleket is belevettem a dologba, de ettől eltekinthetünk , úgy is érdekes a feladat.)
(A feladat csak egy beszélgetés közben 'keletkezett' egy másik fórumon, szóval a megoldásáról semmit nem tudok, (nem tudtam megoldani), érdeklődéssel olvasom itt a fejleményeket.)
pontosabban a kitevőket hol innen, hol onnan néztem. ennélfogva igaz, ha a=2-ből van max 3 db, a=3-ból max 2, és a többiből max 1, de ekkor a fut egészen 10k/2-ig, és a felső becslés lesz 10k/2+ pár.
Nem tudom mennyire érinti a lényeget (azt ugyanis nem értem), de 1...10k-ig 10k/2 négyzetszám, 10k/3 köbszám, ..., 10k/n n. hatvány van. Ennélfogva 10k és 10k+1 között 10(k+1)/2-10k/2=10k/2(101/2-1) négyzetszám,... van. Aztán egy szitaformula használatával (mert a köbszámok között vannak négyzetszámok, és viszont) talán meg lehet becsülni a hatványok számát 10k és 10k+1 között, ami szerintem a nagyobbik szám négyzetgyökének a nagyságrendjébe esik.
Gondolom a feladat megalkotói nem erre gondoltak, de nyilván van egy triviális trükkös megoldás. Használjuk az alábbi kódolást: 0..9 - értelemszerű jelentéssel - = 10 + = 11 / = 12 * = 13 ( = 14 ) = 15
Így 16-os számrendszerben tudom kódolni a számokat, az meg nyilván tömörebb mint a 10-es szémrendszer már 100 ezer feletti számokra is. A 255 kódolása például )), az 1024 kódolása meg 400.
De ez gondolom csalás, úgyhogy valami szabályosabb megoldást kellene találni. Én is a hatványok irányában tapogatóznék.
A karakterek számával exponenciálisan növekszik a számok száma. A hatványok száma meg qligeti alapján lasabban nő, vagyis egyre nagyobb karakterszámú számoknál egyre kisebb részt fednek le a hatvány alakok. A megmaradó (100%-hoz tartó) egyéb számokat meg a nem tömörítő pluszminuszos formulával kellene lefedni, amiről tudjuk hogy nem megy.
Beírtam a tippemet, szerintem van 'rövidebb' hatvány formula mint a tízes számrendszerbeli leírás (ami persze szintén hatványformula, csak az alap rögzített).
A dolog lényege, hogy a szorzás, összeadás, kivonás stb. önmagában triviálisan nem alkalmas kevesebb karakteres felírásra.
Dióhéjban:
Csak a hatvány képlet képes több karakteres tizes számrendszerbeli számot létrehozni, mint ő maga. A hatványok közötti lyukakat (olyan számokat amiknek nincs hatvány alakjuk) ki kell tölteni sima összeadás-kivonás stb, toldalékokkal, amik viszont nem tömörítenek sőt.
Na most, ha sok a lyuk a hatványok között, akkor a sokféle lyukat sokféle különböző számmal kell kitölteni, ezek pedig sok karaktert jelentenek.
A példádban azt, amit 3-jeggyel tudsz leírni normál 10-es számrendszerbeli alakjában, a jobboldalon leírtad 17 karakterrel (vagy 20-szal, ha a hatványozás jele a ^). Jobbal leírható úgy, hogy 123=11^2+2, ami csak 6, ill. 2^7-5, ami csak 5 karakter (esetleg 4, ha a hatványozáshoz nem kell jel 27-5), de egyik sem rövidebb, mint a triviális leírás.
Persze a 10^10 rövidebben leírja a 10000000000-et, de ez a ritka kivétel. A bizonyítás vázlata lejjebb: a hatványszámok ritkák.
Mármint mi igaz? qligeti _bizonyította_ hogy nem meg kevesebb karakterrel mint a tízes számrendszerbeli szám maga, ha nem is varrta el a részleteket. De a lényeg megvolt.
