1

Given any number with random digits, can you always arrange sequential primes in such a way where that number can be formed? Example: $31017643$ is broken into $3,101,7,643$ given all of those are prime.

Of course we can eliminate every number that ends in 0, 2, 4, 5, 6, and 8.

I wrote some code to test this, and it gets out of hand very quickly.

Has someone 200 years ago already solved this? How would I go about proving or disproving this idea?

TobsterStrudel
  • 11
  • IMO such problems are not vewy interesting because they depend on the representation of a number. This means in a different representation like base-16 you'll get different results, and a finding doesn't really tell anything about the number in question. – emacs drives me nuts Aug 20 '22 at 07:27
  • 2
    How would you do this for 21? – lisyarus Aug 20 '22 at 07:27
  • @emacsdrivesmenuts it certainly does tell you something about a number, e.g. whether it is representable as sum of primes multiplied by powers of ten. Anyway, whether this question is interesting or not is subjective; I personally am not a huge fan of axiomatic geometry, but I'd find it rude to comment those questions as being not interesting. – lisyarus Aug 20 '22 at 07:38
  • 2
    @lisyarus That's fair, you can't. 215, 2156, also don't work. I guess counter-examples could continue to be thought up. Case closed. – TobsterStrudel Aug 20 '22 at 07:39
  • 1
    @emacsdrivesmenuts It is true that math that depends on which base you are in has a distinct flavor, and I can respect people who don't like it. Yet we have things like the $p$-adics, which is basically base-$p$ arithmetic (for a prime $p$) taken to the extreme, and that's a prolific area of extensive research. (Also, have you tried Vim? Or maybe even Neovim? ;-P) – Arthur Aug 20 '22 at 08:00
  • 1
    @TobsterStrudel It might still be an interesting question (depending on people's definition of "interesting") to see how likely it is that a random integer can be broken up like this (ignoring those $n \equiv 0,3,4,5,6,8 \pmod{10}$, so really only 40% of the number line). Not sure how readily attackable that is but hey, recreational mathematics is like that. – Eric Snyder Aug 20 '22 at 10:22
  • 1
    @EricSnyder I agree that the probability would still be interesting. You mean of course that $2$ mod $10$ must be ruled out instead of $3$ mod $10$. But the last digit can be $2$ or $5$ , if the second last is then one of $1,3,7,9$. And for example all numbers containing only of the digits $2,3,5,7$ also do the job. But $4,6,8$ must definitely be ruled out as an ending digit. – Peter Aug 20 '22 at 13:33

1 Answers1

1

The question was already answered in the comments, but I decided to post a kind of an extended answer.

First of all, I don't think we should exclude numbers that end in 2, because e.g. 32 can be broken into 3 and 2, both of which are primes. The same goes for numbers ending in 5.

Even without this suggestion, here are all the numbers below 100 that end in 1, 3, 7, or 9, and that cannot be represented as a concatenation of primes in base 10: 9, 21, 39, 49, 51, 63, 69, 81, 87, 91, 93, 99. Here is a C++ program that computes them by simultaneously maintaining a list of prime numbers and a bitmask telling which numbers are prime.

Using the same approach (and switching to 64-bit integers; here's the full code: it won't run online due to time limit restrictions - it ran for 16 minutes on my i9 machine), I computed all numbers less than one billion that cannot be broken into primes (including those ending in 0, 2, 4, 5, 6, 8): there happen to be 711970152 of them (about 71%).

So, if we assume that numbers ending in 0, 2, 4, 5, 6, 8 cannot be broken into primes (as I've said above, this isn't entirely true for 2), among the remaining 40% of all numbers about 3/4 can be broken into primes.

If instead we only exclude number that definitely cannot be broken into primes, i.e. numbers ending in 0, 4, 6, or 8, that constitute 40% of all numbers, among the remaining 60% about half (slightly less than a half, to be precise) of these numbers can be broken into primes, and about half cannot be.

lisyarus
  • 15,517
  • The main problem of a simulation is that there is probably no efficient way to enumerate all possible breaks for a large number (say with $500$ digits). It would be nice if you could describe how you were able to check the range upto $10^9$ so quickly. – Peter Aug 20 '22 at 15:46
  • 1
    @Peter Sure, the performance gets worse as numbers grow. The algorithm works by trying to split a number as a concatenation of A and B with B being prime and recursively checks whether A can be broken in the same way (A is allowed to be empty, in which case B must be a prime). To speedup checking for primes, I maintain an array with array[N] saying whether a number at index N is prime. – lisyarus Aug 20 '22 at 19:52
  • 1
    @Peter Since numbers larger than N cannot participate in splitting N, I only need to know all the primes less than or equal to N. The final algorithm just iterates over N up to $10^9$, fills the prime array by checking whether it is a prime, and then checks whether it can by split into primes using the primes array. – lisyarus Aug 20 '22 at 19:52
  • Thank you for coding this! The analysis afterwards is also great appreciated. I'm going to look for a pattern that occurs in these "prime-separable" numbers. – TobsterStrudel Aug 22 '22 at 02:43