İstediğin şartlarla birazcık oynarsak en azından $1$'den büyük rasyonel sayıları taban olarak kullanabiliriz.
Kanıtlayacağımız şey şu: $a > b$ pozitif doğal sayılar olsun. Her $n \in \mathbb{N}$ doğal sayısını $0 \leq c_0, c_1, \ldots, c_k < a$ olmak üzere $$ n = c_0 + c_1 \left( \frac{a}{b}\right) + c_2\left( \frac{a}{b}\right)^2 + \ldots + c_k \left( \frac{a}{b}\right)^k$$ şeklinde yazabiliriz. Üstelik bu yazılımı tek bir biçimde yapabiliriz.
Örnek: Mesela $13$ sayısını $3/2$ tabanında yazalım: $$13 = 1 + 2 . \frac{3}{2} + \left( \frac{3}{2}\right)^2 + 2.\left( \frac{3}{2}\right)^3$$ İnanmayan kontrol edebilir.
Neden?
Genel duruma geçmeden önce bildiğimiz örnekleri inceleyelim.
$10$'luk taban: Öncelikle en bildiğimiz taban aritmetiğini inceleyelim. Eğer Babil'de Hammurabi zamanında doğup büyümemişseniz, büyük ihtimalle sayıları onluk tabanda yazıyorsunuz. Peki bu yazılımı nasıl yapıyoruz? $24$ ne demek mesela? $24$ demek, onluk açılımda $24 = 4 + 2 . 10$ demek. Ya da $1234 = 4 + 2.10 + 3.100 + 1000$. Bildiğimiz basamak değeri, sayı değeri falan filan. Bunu şöyle görebiliriz:
Diyelim ki elimizde yirmibeş tane yumurta var. $$\bullet \bullet\bullet\bullet\bullet\bullet\bullet \bullet \bullet \bullet\bullet\bullet\bullet\bullet\bullet \bullet\bullet \bullet\bullet\bullet\bullet\bullet\bullet \bullet\bullet$$ Bunları onlu onlu gruplandıralım: $$(\bullet \bullet\bullet\bullet\bullet\bullet\bullet \bullet \bullet \bullet)(\bullet\bullet\bullet\bullet\bullet \bullet\bullet \bullet\bullet\bullet)\bullet\bullet\bullet \bullet \bullet$$ Yaptığımız tam olarak $25$i $5 + 2.10$ şeklinde yazmak. Bu her onlu grubu böyle yazmak yerine tek bir yumurta ile gösterelim, ama bu tek yumurtanın on tane yumurtayı temsil ettiğini göstermek için araya çizgi koyalım:
$$\bullet \bullet \bullet \bullet \bullet | \bullet \bullet$$
Çizgiden sonraki yumurtalar $2 \times 10$ sayısını gösteriyor. Çizgiden öncekiler de $5 \times 1$.
$2$'lik taban: Bu da bilgisayarlarımızın kullandığı taban. Burada iki tane rakamımız var: $0$ ve $1$. Mesela $11$ demek $1 + 1 . 2$ demek oluyor ikili yazılımda. $1101$ demek $1 + 1 . 2 + 1 . 2^3$ demek oluyor. Eğer taban aritmetiğiyle biraz oynamışsanız bunları zaten biliyorsunuzdur, eğer daha ilkokula falan gidiyorsanız biraz oynayarak kendinizi alıştırabilirsiniz. Şimdi elimizde yine yirmibeş tane yumurta olduğunu varsayalım. Bunun ikilik tabandaki gösterimi ne? Bakalım. Bütün yumurtalarımızı koyalım yine: $$\bullet \bullet\bullet\bullet\bullet\bullet\bullet \bullet \bullet \bullet\bullet\bullet\bullet\bullet\bullet\bullet \bullet\bullet \bullet\bullet\bullet\bullet\bullet\bullet \bullet$$ Şimdi bunları onlu onlu gruplandırmak yerine ikili ikili gruplandıralım: $$(\bullet \bullet)(\bullet\bullet)(\bullet\bullet)(\bullet \bullet) (\bullet \bullet)(\bullet\bullet)(\bullet\bullet)(\bullet \bullet)(\bullet \bullet)(\bullet\bullet)(\bullet\bullet)(\bullet \bullet)\bullet$$ Şimdi yukarıda yaptığımızı yapalım ve her ikili grubu tek bir yumurta ile gösterelim ama bunu yaptığımızı belli etmek için araya bir çizgi koyalım: $$\bullet | \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet$$ Çizginin sağında çok fazla yumurta var. Bunları da ikili ikili gruplandırıp aynı şeyi yapalım: $$\bullet | (\bullet \bullet) (\bullet \bullet) (\bullet \bullet) (\bullet \bullet) (\bullet \bullet) (\bullet \bullet) \\ \Downarrow \\ \bullet | \quad | \bullet \bullet \bullet \bullet \bullet \bullet \\ \Downarrow \\ \bullet | \quad | (\bullet \bullet) (\bullet \bullet) (\bullet \bullet) \\ \Downarrow \\ \bullet | \quad | \quad | \bullet \bullet \bullet \\ \Downarrow \\ \bullet | \quad | \quad | (\bullet \bullet) \bullet \\ \Downarrow \\ \bullet | \quad | \quad | \bullet | \bullet$$ Şimdi ne yaptığımızı hatırlayalım: $1 + 0.2 + 0.2^2 + 1 . 2^3 + 1.2^4$ yaptık tam olarak. (Gerçekten de 1 + 8 + 16 = 25 yapıyor.) Bu örnek önemli bir örnek. O yüzden buraya kadar olan yeri çok iyi anlamış olmak önemli.
En baştaki örneğe geri dönelim: $13$'ü nasıl yazdık $3/2$ tabanında? $13$ yumurtamız var diyelim ve hepsini ortaya koyalım:
$$ \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet $$ ve bunları üçer üçer gruplandıralım:
$$ (\bullet \bullet \bullet) (\bullet \bullet \bullet) (\bullet \bullet \bullet) (\bullet \bullet \bullet) \bullet $$ Şimdi bu üçlü gruplardan her birini iki yumurtayla temsil edelim ve bunu yaptığımızı belirtmek için bir çizgi çizelim:
$$\bullet | \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet$$ Görüldüğü gibi dört tane üçlü grubumuz vardı, dolayısıyla ikinci kutuya sekiz tane yumurta geçirdik. Aynı şeyi tekrar ve tekrar yapalım.
$$\bullet | (\bullet \bullet \bullet)( \bullet \bullet \bullet) \bullet \bullet \\ \Downarrow \\ \bullet | \bullet \bullet | \bullet \bullet \bullet \bullet \\ \Downarrow \\ \bullet | \bullet \bullet | (\bullet \bullet \bullet) \bullet \\ \Downarrow \\ \bullet | \bullet \bullet | \bullet | \bullet \bullet $$ Şimdi bunu okuyalım: $$1 + 2 . \frac{3}{2} + \left( \frac{3}{2}\right)^2 + 2.\left( \frac{3}{2}\right)^3$$ ve bu tam olarak da $13$'e eşit.
Genel Algoritma
O zaman algoritmamızın ne olduğu açık artık: Elimizdeki $n$ sayısıyla başlayacağız. $a$'lı gruplara ayıracağız. Yani $n$'i $a$'ya böleceğiz. Kaç tane grup varsa (bölüm), bunun b katını bir sonraki kutuya geçireceğiz. Kalanlar kalacak. Şimdi ikinci kutu için aynı şeyi yapacağız. Bunu yapabildiğimiz kadar yapacağız. İşlem bittiğinde kutularda kalan sayıları okuduğumuzda istediğimiz yazılımı bulacağız.
Bunun işe yarayacağını görmek çok zor değil ama yine de kanıtlanması gereken bazı şeyler var. Bunların ne olduğunu yazacağım ama kanıtlamayacağım:
1) Bu algoritma sonsuza kadar sürmez. Eninde sonunda durur.
2) Algoritma durduğunda her kutuda kalan yumurta sayısı $a$'dan küçük olur.
3) Bu algoritma gerçekten istediğimiz yazılımı verir.