Finding Prime Numbers in 2010: Is It Possible?

[sachinism]

Is it possible to write the 2010 numbers from 1 a 2010 in some order so that the
6933 digit number you get is prime?

 

[CRGreathouse]

http://www.jimloy.com/number/nines.htm

 

[Wizlem]

I get 4/10*2009! ways to do it. It helps to know the 6933 digit is the last digit.

 

[CRGreathouse]

Hint: 1 + 2 + ... + 2010 = 2010 * 2011 / 2.

 

[Bill Simpson]

This does not answer or perhaps even hint at an answer to the original question, but 2010 is not 3n+1.
For 3n+1 numbers concatenated you can extremely quickly find a "prime permutation."
4,1423
7,1234657
10,12345678109
13,12345678910121311
16,12345678910111214161513
19,12345678910111213141517181619
22,12345678910111213141516172218201921
25,12345678910111213141516171819202325222421
28,12345678910111213141516171819202122252724282623
31,12345678910111213141516171819202122232425262831302729
...
For other than 3n+1 there are either no solutions (for small n) or it can take a very long time and I do not know whether there are solutions or not.

This surprising behavior persists up to at least 157.
Why? It seems like there should be a good answer for this.

 

[CRGreathouse]

2010!=3n+1.

It's not... all factorials of numbers >= 3 are of the form 3n.

 

[CRGreathouse]

I get 4/10*2009! ways to do it. It helps to know the 6933 digit is the last digit.

That's not right, either.

 

[Wizlem]

I think this problem needs clarified because what I understood it to be is obviously different than everyone else. I saw the problem as simply writing the numbers down in order to create one big long number. For instance if you write the numbers from 1 to 3 in some order you can get 123 132 213 231 312 or 321. It seemed even more likely(to me) this was the problem when you add up the number of digits in each number from 1 to 2010 and get 6933 which is the digit asked for. At that point I saw it as simply taking out a number which ended with 2, 3, 5 or 7 and writing all the rest in any order you wish followed by the number you took out.

 

[hamster143]

For instance if you write the numbers from 1 to 3 in some order you can get 123 132 213 231 312 or 321.

It would do you good to observe that all six of these permutations are divisible by 3.

You could then try to generalize that observation.

 

[Bill Simpson]

When the original poster wrote "write the 2010 numbers from 1 a 2010 in some order so that the 6933 digit number" I read that to mean "does there exist a permutation of the 2010 numbers such that all their digits then concatenated"

When I first wrote "but 2010!=3n+1" I did not mean to imply 2010 factorial and instead meant "but 2010 is not equal to 3n+1" and I later edited that sentence to try to be more clear.

When I then wrote that I observed a pattern for 3n+1 numbers I have now expanded that claim.

For numbers m up to 301 a prime formed from the concatenation of the digits of a permutation of the numbers 1...m can be found in the first 7 factorial permutations I inspect for all numbers of the form 3n+1 except for 160, 172, 271, 283 and 298 and for none of the numbers of the form 3n or 3n+2. For 160 no "prime permutation" was found in the first 2924903 permutations inspected, but I expect that with more permutations inspected that a prime will be found.

It appears that the number of permutations that must be inspected to find a prime is a slowly growing function of n, as I would expect, so it is not too surprising that for larger m there are more examples of numbers that are resistant to finding a "prime permutation" in the first 7 factorial permutations, with the permutations enumerated in lexographic order I believe.

Just to be clear, that 7 factorial threshold I used has no deep significance. I simply looked at the last few permuted numbers in each discovered prime and saw that initially usually 7 or fewer were interchanged.

 

[CRGreathouse]

For numbers m up to 301 a prime formed from the concatenation of the digits of a permutation of the numbers 1...m can be found in the first 7 factorial permutations I inspect for all numbers of the form 3n+1 except for 160, 172, 271, 283 and 298 and for none of the numbers of the form 3n or 3n+2. For 160 no "prime permutation" was found in the first 2924903 permutations inspected, but I expect that with more permutations inspected that a prime will be found.

2010 isn't of the form 3n+1, though.

 

[Wizlem]

It would do you good to observe that all six of these permutations are divisible by 3.

You could then try to generalize that observation.

I'm not sure why this is of any use and would do me good but I will go ahead and generalize it.

Any (base 10) number whose digits are the permutation of the digits of a number which is divisible by 3 is divisible by 3. I will leave it up to the reader to prove that any permutation can be represented by a series of permutations which simply swap 2 items. Suppose you have a number n and you flip the p and q digits and they're corresponding values are a and b. The resulting number will be

n+a\cdot10^q-b\cdot10^q+b\cdot10^p-a\cdot10^p=n+a(10^q-10^p)-b(10^q-10^p).

We can arbitralily say p<q so we can write the number as

n+a\cdot10^p(10^{q-p}-1)-b\cdot10^p(10^{q-p}-1).

It is easy to see that that 10^{q-p}-1 is divisible by 3 so the new number is the sum of terms which are all divisible by 3 and so is divisible by 3.

It follow that if you take the numbers from 1 to 3n and concatenate their digits in some order the resulting number is divisible by 3. This is true for n=1 simply by checking. Assume it is true for some k. We only have to show that the next 3 numbers concatenated to the end of any permutation of the numbers up to 3k in counting order is divisible by 3. Now it is easy to see that 3n-1, 3n-2, and 3n all have the same number of digits. If one had more digits than the others (either 3n-1 or 3n-2), then a number smaller than it would be of the form
10^p-1 for some p. However, this number is divisible by 3 and so could not be 3n-1 or 3n-2. Let s be the number of digits of 3(k+1) and r be a permutation of the numbers up to 3k. Now consider the number

r\cdot10^{3s}+(3n-2)10^{2s}+(3n-1)10^{s}+3n=r\cdot10^{3s}+3n10^{2s}+3n10^s+3n-(2\cdot10^s+1)10^s.

This number is a permutation of the numbers from 1 to 3(k+1). Since 21 is divisible by 3 and by the previous proof 2 followed by s zeros followed by 1 is divisible by 3. Therefore this permutation is the sum of numbers divisible by 3 and is divisible by 3. By induction, the proof is complete.

It follows that no permutation of the 2010 numbers is prime.