Hamming Sayıları Nedir?

Hamming sayıları ilk kez Richard Hamming tarafından tanımlanmış bir sayı dizisidir Bunlar pozitif tamsayılar olup çarpanları sadece 2, 3 ve 5'in kuvvetleridir İlk birkaç Hamming sayısı şunlardır: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, Hamming sayıları k-düzgün sayıları denen sayılar kategorisinin bir özel halidir Bu tür sayıların kdan büyük asal çarpanı yoktur Dolayısı ile Hamming sayıları da 5-düzgün sayılardır Hamming sayılarını artan sırada hesaplama algoritmaları Edsger Dijkstra tarafından yaygınlaştırılmıştır
Dijkstra'ya göre Hamming sayılarını hesaplamak 1'den büyük ve 2, 3 veya 5 haricinde asal çarpanı olmayan, yani 2^i x 3^j x 5^k (i,j,k ≥ 0) şeklindeki, sonsuz sayı dizisini kurmak demektir Bunu hesaplamak için aşağıdaki adımlar takip edilir

h bir Hamming sayısı ise 2h, 3h ve 5h de Hamming sayılarıdır
1 bir Hamming sayısıdır ve hesaplamayı başlatmak için kullanılır
Dizinin sıralı olması için 2, 3 ve 5 ile çarpmadan gelecek ve henüz kullanılmamış olan sayıları kıyaslamak yeterlidir Diğer çarpımlar bunların bir kısmından daha büyük olacaktır, dolayısı ile sıralı listedeki ilk eleman olamazlar

Bu algoritma sık sık tembel fonksiyonel programlama dillerinin gücünü göstermek için kullanılır çünkü böyle bir dilde yukarıdaki adımları doğrudan uygulamak mümkün iken bir katı fonksiyonel programlama dili ile ya da bir imperatif programlama dili ile bunu gerçekleştirmek basit bir iş değildir