Unique Prime Factors in a uint(32) or even a uint(64)

Users
1

I am trying to port a Fortran routine to Chapel. I probably only need the answer for a uint(32). It is for the number of points in a mixed radix FFT.

To simplify the coding, it would be advantageous to know the maximum number of unique prime factors in a uint(32). With at most 26 significant bits in a uint(32)., the number is 8 if you ignore the fact that 1 is a prime factor of every number.

Where would I look for this answer?

Thanks.

2

Hi Damian -

To my understanding, you are asking a question about number theory. If you know a number theorist, it might be time to ask them.

Anyway, I'm not a number theorist, but with some searching I have identified some material that might help you:

As I said, I'm not a number theorist, so there very well might be something wrong in this reasoning, but hopefully it gives you enough to go on.

3

Thanks for the tips. I do not know any number theorists.

Thanks for the advice.

I have learnt more about prime numbers in the last week than I ever really wanted to know. I learnt a lot more about prime gaps and how to compute them optimally.

My 30 year old C code to factor N did not port so well so I looked for a better algorithm. When I looked at that code with hindsight, I (thankfully) realized that my programming skills had improved over that time because I looked at that old code somewhat disapprovingly.

I have run my code to factorize every integer up to about 2^31 and it works and your formula confirms those tests of mine. That will suit the client's limit on the number N which they need to be able to factorize. But I would like the code to be totally general, especially as Chapel's default integer is 64 bits and maybe the code needs to last another 30 years. A scary thought.

The Chapel code returns a 2D array [1..n,1..2]. When I rewrote it in C, that new C code is way cleaner than what I started with. So Chapel encourages or (I would almost say) mandates a better programming style. Also, I note than CLANG 15 runs nearly twice as fast as GCC 11 for this purely integer algorithm.

Thanks again for your help.

1 Like
4

Your reasoning certainly seems to be on the right path. Given a number X between 1 and 2^n such that

primorial(p) < 2^n < primorial(p+1)

then testing for n in 1..14 shows that X has at most p unique prime factors. I will run the cases of 15, 16 and 17 and 18 overnight to confirm but it seems like the above holds. Note that either or both of those inequalities might be the looser less than or equals to. I might even try 19, 20, 21 and 22 but it certainly looks like your formula has the answer.

Thanks again.

Yes, I could save the unique primes in a list and then allocate the size of the array at the end to capture the unique primes and the number of times each such prime occurs in the factors of the number in question, but I want something a little more predictable than that. Also, programming it is C with an array only uses 133 lines of assembler with GCC11 or 141 lines with CLANG15. As soon as you use a linked list, it blows out the lines of assembler code and slows it down slightly. Besides, clients who long ago were Fortran programmers are most happy with an array.

Your search skills are certainly superior to mine. When I went fishing for clues, the only useful thing I learnt is that there is a relationship which the gap between primes satisfies. Not a predictable formula, but a relationship which means you do not have to go looking for a prime when is just the next odd number. Fascinating. Mind you, I think I will stick to numerical analysis. Number theory seems a bit too esoteric for me.

Now I can get onto the main game which is to port the C++ code of an FFT for an arbitrary number of points into Chapel.

5

Slightly more robust reporting of results to date - 3 larger numbers are running. I factorize every number up to N^2-1 and the number in the #F column is the most factors I found. I note the primorial bounds between which N^2-1 lays.

              N  #F             N^2-1
            1024 (7): P(7) <   1048575 < P(8)
            2048 (7): P(7) <   4194303 < P(8)
            4196 (8): P(8) <  17606415 < P(9)
            8192 (8): P(8) <  67108863 < P(9)
           16385 (9): P(9) < 268468224 < P(10)
           32769 (9): P(9) < 1073807360 < P(10)
           65537 (9): P(9) < 4295098368 < P(10)
1 Like