puzzle

[Don Shepherd]

How many 4-digit arrangements of the digits of the number 1232 are prime?

How many 4-digit arrangements would you have to check?

Is there a way to check other than an electronic prime factor finder or our old friend, brute force?

[Thomas Klemm]

(06-29-2018 03:40 AM)Don Shepherd Wrote:  How many 4-digit arrangements of the digits of the number 1232 are prime?

Code:

Spoiler Alert












3

1223
2213
3221

Quote:How many 4-digit arrangements would you have to check?

Code:

Spoiler Alert












12 = 4! / 2!

1223
1232
1322
2123
2132
2213
2231
2312
2321
3122
3212
3221

Quote:Is there a way to check other than an electronic prime factor finder or our old friend, brute force?

Code:

Spoiler Alert












Even numbers are rarely prime:
1232
1322
2132
2312
3122
3212

Check alternating sum of digits:
2123 -> 2 - 1 + 2 - 3 = 0 => divisible by 11: 2123 = 11 * 193
2321 -> 2 - 3 + 2 + 1 = 0 => divisible by 11: 2321 = 11 * 211

Brute force:
2231 = 23 * 97

That was fun.

[ijabbott]

(06-29-2018 04:27 AM)Thomas Klemm Wrote:  

(06-29-2018 03:40 AM)Don Shepherd Wrote:  How many 4-digit arrangements would you have to check?

Code:

Spoiler Alert












12 = 4! / 2!

1223
1232
1322
2123
2132
2213
2231
2312
2321
3122
3212
3221

Code:

Spoiler Alert









6 if you initially discount the even numbers by inspection - there are only two choices for the units digit.

(You have filtered out the even numbers out in the next step.)

Quote:

Quote:Is there a way to check other than an electronic prime factor finder or our old friend, brute force?

Code:

Spoiler Alert












Even numbers are rarely prime:
1232
1322
2132
2312
3122
3212

Check alternating sum of digits:
2123 -> 2 - 1 + 2 - 3 = 0 => divisible by 11: 2123 = 11 * 193
2321 -> 2 - 3 + 2 + 1 = 0 => divisible by 11: 2321 = 11 * 211

Brute force:
2231 = 23 * 97

Code:

Spoiler Alert












You could also do an initial sum over the digits:

1+2+3+2 = 8

Not a multiple of 3, so it is worth considering other checks for primality. If the given number was 1233, it would fail this initial test - all arrangements would be divisible by 3.

Quote:That was fun.

I really wish there was a [spoiler]spoiler[/spoiler] tag!

[Don Shepherd]

Thanks Thomas and Ian.

Wow, I learned something new today, the divisibility by 11 test.

Don

[Thomas Klemm]

(06-29-2018 12:15 PM)Don Shepherd Wrote:  Wow, I learned something new today, the divisibility by 11 test.

That's because 10 ≡ -1 (11); that is modulo 11.
Hence 10² ≡ 1 (11), 10³ ≡ -1 (11), 10⁴ ≡ 1 (11) and so on ...

A number say 4153 can be written as 4⋅10³ + 1⋅10² + 5⋅10¹ + 3⋅10⁰.
So we end up with: 4153 (11) ≡ 4⋅(-1) + 1⋅1 + 5⋅(-1) + 3⋅1 (11) ≡ - 4 + 1 - 5 + 3 (11) ≡ -5 (11) ≡ 6 (11).
And then of course if the remainder is 0 the number is divisible by 11.

There are a lot of other divisibility rules.

For 23 we have:

Quote:Add 7 times the last digit to the rest.

2231
223 + 7⋅1 = 230
23 + 7⋅0 = 23

Thus we can conclude that: 23 | 2231

The reason is that since 70 ≡ 1 (23) we get:
7⋅(10a + b) ≡ 70⋅a + 7⋅b ≡ 1⋅a + 7⋅b ≡ a + 7⋅b (23)

Now 7 doesn't divide 23, so we see that:
10a + b ≡ 0 (23) ⇔ a + 7⋅b ≡ 0 (23)

This magic number can be found for each prime p as the multiplicative inverse of 10 in ℤ_p.

For p = 23 we have 7 since 7⋅10 = 70 ≡ 1 (23)
For p = 7 we have 5 since 5⋅10 = 50 ≡ 1 (7)

We can use the Euclidean algorithm to find this number for e.g. p = 17.

We just try to represent the remainder r in each step as:
r = a⋅10 + b⋅17 for integer values a and b.

7 = 17 - 10 = -1⋅10 + 1⋅17
3 = 10 - 7 = 2⋅10 - 1⋅17
1 = 7 - 2⋅3 = 3⋅17 - 5⋅10

Thus we end up with: 1 ≡ - 5⋅10 (17)
And thus the magic number is -5. Or 12 if you prefer since both are the same modulo 17.

This explains the mentioned rule:

Quote:Subtract 5 times the last digit from the rest.

[brickviking]

(06-29-2018 03:40 AM)Don Shepherd Wrote:  How many 4-digit arrangements of the digits of the number 1232 are prime?

How many 4-digit arrangements would you have to check?

Is there a way to check other than an electronic prime factor finder or our old friend, brute force?

Before I read any other posts, there are only two arrangements you'd have to check. The rest are not prime. Now I'd better go read the rest of the thread...

(Later) I'd forgotten about a couple of the others, and was basing my theory on anything ending in 1 or 3, regardless of what the other digits were. My only mistake was that not all the possible numbers began with 22. :/

Personally, I'd just do it by brute force, there aren't that many combinations to check.

(Post 253)