Math Problem (possible solution with Mathematica)

Factual Questions
1

Hello fellow dopers.

For fun ( and a free cookie ), I am trying to solve a math problem. Before any further comments, here is the problem in full:

“Show that the seven consecutive digits 2, 3, 4, 5, 6, 7, 8 can be arranged in 5040 different orders giving 5040 distinct seven digit integers, but none of these is a perfect square.”

First brainstorm has me putting the numbers 2 3 4 5 6 7 8 in a permutation. Then after the perm, I would filter the results to eliminate the non-perfect square answers.

This, if I correctly assume, is the easy answer to the problem – not having to solve long hand, which I’m not sure how to attempt and if anybody would be willing to help with that, I would be willing to share my cookie.

Anyways, back to my original plan…

I use Mathematica, which is basically a calculator on crack for your computer. I am attempting the problem via my original method, and I start with the perm.

“Permutations[{2, 3, 4, 5, 6, 7, 8}]” gives me all the possible resulting combinations. Here is where I run into the wall. The answers are in this format "{2,3,4,5,6,8,7} etc., etc. What I need to do is pull them out of this format and make them whole integers and then run a filter on the resulting integers to eliminate all possible perfect suqares.

Any genius dopers with experience in Mathematica that can help me out?

Thanks in advance.

Yesterdog

2

I don’t do Mathematica, but generating all the numbers and testing each one for squareness seems inefficient.

It would be better, I think, to find the square roots of the smallest and largest values, calculate the squares of all the integers in that range, and check each for the proper digits. The bounds, to two digits precision, are 1531.56 and 9938.08, so check the squares from 1532 to 9938 inclusive. Extract successive digits using DIV() and MOD(), and mark them off in an eight-element array.

The proper way, at least for a mathematician, would be to prove it without all the arithmetic, but I have no idea even how to approach that.

3

Brute force has a proud history in applied mathematics, so don’t go discounting it just yet.

4

Hmm…I don’t have Mathematica at home so I can’t check my syntax, but it sounds like for the first part you want to use Map to apply an anonymous function to each element of the list.

i.e., something like



Map[ 1000000 #[[1]] + 100000 #[[2]] + 10000 #[[3]] + 1000 #[[4]] + 100 #[[5]] + 10 #[[6]] + #[[7]] &, Permutations[{2, 3, 4, 5, 6, 7, 8}]

(Assuming I haven’t screwed something up; I’m working from memory here.)

Then store the result in a list L and use “Select[L, IntegerQ[Sqrt[#]] &]” to pick out the non-squares.

5

After telnetting to my work account I learned that I did screw up the syntax: I left out a closing “]”.

6

I’m with rjk – there will only be a few thousand perfect squares to hunt through, and even fewer if you trim the possibilities as follows. Take a look at this table:

n : last digit of n[sup]2[/sup]
0 : 0 – out
1 : 1 – out
2 : 4 – in
3 : 9 – in
4 : 6 – in
5 : 5 – in
6 : 6 – in
7 : 9 – in
8 : 4 – in
9 : 1 – out

30% of your potential roots are eliminated straightaway. Now use your division rules: 2+3+4+5+6+7+8 = 35 (not divisible by 3) so another third of the root candidates you were going to test has been eliminated.

Looking at the chart above, you can also see that if it’s a square made of your seven digits, it must end in 4, 9, 6, or 5. I’ve just shrunk your search space by more than 60%, because you also know that none of the squares in the range 4,000,000-4,999,999 can meet your criteria if they end in 4 (and so forth).

Got all those rules coded into Mathematica? Good. Now brute force it. It’ll be, like, three seconds faster. :smack:

7

This site suggests that there are only 22 choices for the last two digits of a perfect square:

00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96

Given that you’re only using the digits 2, 3, 4, 5, 6, 7 and 8, you should be able to narrow down the testing process even further.

8

I believe the correct range of roots is 1520 to 2960.

Jurph should have eliminated roots ending in 3 and 7 also.

If you had a means of squaring each possible root and summing the digits, you possibly could eliminate a truckload --any possible square must sum 35.

9

Fingers on wrong keys – range 1532 to 2960.:smiley:

10

On that Mathworld page, there’s also a statement which allows us to eliminate all of the OP’s numbers in one swell foop, with no brute force required… But on the off chance that this is a homework problem, I’ll refrain from saying exactly what it is until tomorrow.

11

Yes, that’s the range. I typed ‘8765432’ incorrectly. I even thought 9938 looked too big, but didn’t check it. Duh!

The digits-at-end-of-square test didn’t even occur to me, although I remember it now, and summing the digits is great too. And I really like that Map function! Thanks, everybody!

That brute-force approach will get down to pencil-and-paper size yet! (But, ultrafilter, it still ain’t elegant!)

12

We’ve got 1428 possible roots, from 1532 to 2960. However, we know that they can’t end with 0,1,3,7 or 9. This reduces the number of possibile roots to 714.

Doing a little experimenting with cunctator’s list again, I’ve found that the possible roots have to end with:

06 08
16 18
22 24 25 26 28
32 34
42 44
56 58
66 68
72 74 75 76 78
82 84
92 94

hmmm… there’s something to that symmetry. Anyway, that reduces the numbers to be squared to just 370.

13

Any number formed by permuting the numbers 2 to 8 will be equal to 8, or -1, modulo 9. Modulo 9, a square must be equal to 0, 1, 4 or 7. Therefore, no number formed out of those digits is a square.

14

that’s not immediately obvious (to me) but if you think of it in conjunction with what orbifold coded, it makes sense.

15

It’s a slight generalisation of the rule for testing numbers for division by nine. Add the digits of a number in decimal form, then the remainder after dividing by nine is the value of the original number, modulo 9.

16

I’m putting together a purchase order for Mathematica at my company. Can I borrow this phrase for my “Justification of Need”? :stuck_out_tongue:

17

Or, as Mathworld put it,

(that’s about a third of the way down the page). And all of our numbers have digital root 8 (since the sum of the digits is 35, and 3+5=8).

18

First off, I want to thank everyone for helping me out in my quest for the cookie thus far.

This still doesn’t solve my problem of actually getting the roots, or at least showing that there are 5040 distinct integers that aren’t perfect squares…that’s the hard part. Using what I’ve learned here, I could apply these “rules” to my problem, but I think I’m still lacking something to qualify for my cookie.

Still really smart dopers, thanks alot for your help. I’m always up for learning.

Yesterdog

PS. Hyperelastic, only if you do it al la Dave Chappelle style.

19

Yesterdog,

I’m not sure I follow your statement that you still have a problem to solve.

The others postershave established conclusively (and far more ably than I ever could) that there are NO permutations of those digits which are perfect squares. So there’s no need to enumerate the possibilities to look for any.

As to how many permutations there are, that’s basic permutation math. You have 7 things: “2”, “3”, “4”, “5”, “6”, and “7”. In how many ways can you arrange any group of 7 things without repetition? In 7! ways, which is 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040. QED.

So now you know there are exactly 5040 possibilities and exactly zero of them are perfect squares. So there are no roots to calculate.

What’s left that needs solving?

20

You’re right. My idea wasn’t as good as several after that. The Modulo 8 idea is what you need but I don’t know how you prove the conditions stated by other(s).