[Kluring] Hitta en binär sträng i en "sorterad" lista av 2^64 strängar (prog)

Jag såg att detta var olöst, och så kan vi ju inte ha det, så jag spenderade eftermiddagen med att programmera mig fram till lösningen på detta.

Det enda programmeringsspråket jag är bekant med är Java, vars system för att göra aritmetik med stora tal är ganska krångligt, så jag tänkte att jag kanske skulle ge en förklaring av mitt tillvägagångssätt snarare än att bara visa min kod.

Det första att ta itu med är att klura ut hur många ettor talet innehåller. Jag resonerade mig fram till att det finns $\text{nCr}(64,0)=1$ tal med $0$ ettor, $\text{nCr}(64,1)=64$ tal med $1$ etta, o.s.v. (Man kan ju se det som att man väljer ut ett visst antal av $64$ siffror till att vara ettor.). Det betyder att talen med $0$ ettor börjar på index $0$, talen med $1$ etta börjar på index $1$, talen med $3$ på $65$ o.s.v. Med datorhjälp kommer man fram till att talen med $33$ ettor börjar på $10139684107326071075$ och talen med $34$ ettor börjar på $11916774183391613411$. Det $10402927437586948002$:a talet måste därför ha $33$ ettor.

Om man utför subtraktionen $10402927437586948002-10139684107326071075=263243330260876927$ (vårt index minus indexet där talen med $33$ ettor börjar) finner vi att vi söker det $263243330260876927$:e talet med $33$ ettor (räkningen börjar på noll). Jag tänker nu att vi gör en ny lista med bara talen med $33$ ettor.

Nästa steg var att klura ut hur många av talen med $33$ ettor som börjar på noll. Då tänkte jag som så att vi fixerar den första nollan, och har därför $\text{nCr}(63,33)$ val för övriga siffror, vilket enligt multiplikationsprincipen ger att $\text{nCr}(63,33)$ av talen som har $33$ ettor börjar på noll.

$0\underbrace{\boxed{\color{transparent}A}\boxed{\color{transparent}A}...\boxed{\color{transparent}A}\boxed{\color{transparent}A}}_{\text{nCr}(63,33)\ \text{val}}$

Alltså börjar de $\text{nCr}(63,33)=860778005594247069$ första talen på $0$, och eftersom $263243330260876927<860778005594247069$ är den första siffran i vårt tal noll. Vi kan nu göra ett liknande resonemang för den andra siffran. Man ser att $\text{nCr}(62,33)$ av talen som börjar på noll även har noll som andra siffra. Eftersom $263243330260876927<\text{nCr}(62,33)$ får vi att den andra siffran i vårt tal är noll. Proceduren upprepas, och den enda skillnaden ifall vi skulle få en etta (d.v.s. indexet är större än eller lika med binomialkoefficienten) är att indexet då måste justeras till nästa gång genom att subtrahera binomialkoefficienten (ettorna kommer ju efter nollorna).

Man får då till slut att den binära strängen är:

$0010101110011001001011011101111110100010001100100100100111010110$

vilket i det decimala systemet blir:

$3141592653589793238$

men detta mystiska tal känner jag inte igen.

(Dock finns det ett välkänt tal som är ganska precist en $10^{17}$-del så stort :-))

Snyggt jobbat och väl förklarat Alvin.