Wednesday, November 6, 2019

Hamming (5-smooth) numbers

Until quite recently, I was not aware of the idea of "smooth" numbers. This is perhaps better expressed as "N-smooth" numbers (i.e., integers where the largest prime factor is <= N). 5-smooth numbers are also known as Hamming numbers (i.e., an integer of the form 2^i * 3^j * 5^k).




Dijkstra popularized Hamming's query: "Provide an efficient algorithm to enumerate the 5-smooth numbers in sequence".



So, I just started writing down integers, putting their prime factorization underneath them, circling primes and underlining 5-smooth numbers to see if I could see any pattern to the way the factorizations were coming out. I started with 2, circled and underlined it and proceeded to 3 without question.



When I looked up the sequence on OEIS: https://oeis.org/A051037
I felt a fair bit of surprise to see that the sequence started with 1.



So, now I have started to think about things in a way that I had not before...




It seems universal that 2 is accepted as the first prime. And if a prime is simply a number that is divisible only by itself and 1 then, it seems to me like it is a reasonable viewpoint to simply treat 1 as a degenerate case of a number that is only divisible by itself and 1.



So, my primary question is: "Is there clear, unequivocal, objective reasoning that requires 1 to be a 5-smooth number (or prevents it), or is it a bit arbitrary (i.e., dependent on the asker's uses and point of view) whether 1 is included in any such list of N-smooth numbers?" Put another way, is the OEIS answer clearly right or wrong or is it arbitrary?



This led to these other questions that are not immediately obvious to me:



Is it merely a "convention" (a definition of linguistic convenience, if you will) that 1 is not considered the first prime, or is there deeper mathematical reasoning behind that?



Can 0 be in the list of any N-smooth numbers or is it clearly nonsensical to consider that? (This seems rather messy to talk about and I was very tempted to just delete this question from here to simplify things, but perhaps there is some value in including it - I'm not sure.)




What about negative numbers? Is it simply "by convention" that we don't generally talk about the prime factorization of negative integers, or is there clearer mathematical reasoning that necessitates that?



Thanks ;)

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...