5 ms·
Wonder what the limit is as you add more 32 bit integers to the product. Just the primes over 32 bit?
by rao-v 5mo ago
Wonder what the limit is as you add more 32 bit integers to the product. Just the primes over 32 bit?
- thaumasiotes 5mo agoIf you're allowed to multiply as many 32-bit numbers as you want, the only numbers you won't be able to achieve by so doing are those with any prime factor larger than 2^32. This is more than just the prime numbers. For example, a 41-bit prime can be multiplied by 16 and it will still fit into 64 bits.
- deleted 5mo ago[deleted]
- deleted 5mo ago[deleted]
- nyeah 5mo agoWhat are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.
- deleted 5mo ago[deleted]
- shiandow 5mo agoIf you bring overflow into the mix things become a lot more complicated. You likely don't even need 32 bits, the numbers 2 and 3 might be enough (I don't know for sure or if there's a quick way to check).
- thaumasiotes 5mo agoWell, if you "bring overflow into the mix", what you get depends on your behavior when overflowing. If you say that you want to be doing modular arithmetic instead of arithmetic, it doesn't look like 2 and 3 are enough. You're looking for a solution to 2ᵃ * 3ᵇ ≡ n (mod 2⁶⁴) If n is even, we can supply any number of 2 factors by fiddling with a. We can assume without loss of generality that n is odd and a = 0. Now we want 3ᵇ ≡ n (mod 2⁶⁴) for odd n. If I'm reading wikipedia correctly, we know that this will fail for some n: https://en.wikipedia.org/wiki/Primitive_root_modulo_n https://en.wikipedia.org/wiki/Primitive_root_modulo_n > In symbols, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gᵏ ≡ a (mod n). This is what we want, with g = 3, k = b, a = n₁, and n₂ = 2⁶⁴. Our restriction that n₁ (our n) is odd satisfies the requirement that a be coprime to n₂ (wikipedia's n, the modulus). The article continues: > a primitive root exists modulo n if and only if n is 4, pᵏ or 2pᵏ for some odd prime number p and some k ≥ 0. 2⁶⁴ does not satisfy this requirement and therefore there is no primitive root modulo 2⁶⁴. As such, 3 is not a primitive root modulo 2⁶⁴.
- shiandow 4mo agoInteresting, one of those situations where the odd primes behave slightly differently. Which means it's probably above my paygrade. I did say things would get complicated.