I need some help with this math problem. (Teacher allows outside help.)

[mulder]

Ok, I am in Discrete Math 2 and we have a problem we have to pick out and work on. We are allowed to get any and all help, except from teachers at school. Here is the problem I have:

Determine all positive integers with the property that they are one more than the sum of the squares of their digits in base 10.

So, far I have only come up with 35 and 75. My friend and I have been working on a C++ program to do this. We checked all numbers up to 2,500,000. And those two numbers are the only ones that it spits out. I know that there are an infinite number of positive integers, but how can I prove this. From the looks of it 35 and 75 are the only ones, but that is not a proof.

To give you an idea of what the problem means and why 35 and 75 work...

35
--
(3 * 3) + (5 * 5) = 34 and 35 is one greater than 34.

75
--
(7 * 7) + (5 * 5) = 74 and 75 is one greater than 75.

Make sense? Does anyone have any idea on how to prove something like this? Any help would be appreciated. And yes, we do have the teacher's permission to get outside help, just not from out other school teachers.

 

[HomeBrewerDude]

hmmm... i am not a math wiz but heres my 2cents worth:

solve for x

x = 1 + Sum(yi^2)

where
y1 is first digit in x
y2 is second digit in x
etc...

Can you prove no solutions except for where x has 2 digits?

 

[Webbed]

here's what I think the logic is:

start loop from x to 2,500,000 increment 1
x - 1
split x into individual digits
perform the square function (you should loop here again since you don't know the length just let the computer do the keeping track for you)
add it together
then add 1
is the number = x?
yes, print number, then repeat loop
no, just loop

 

[BA]

There's probably a more elegant solution, but

I can prove that there are no 4-digit ones, so there won't be any past 2,500,000.

81*x<10^(x-1) for all x>3

then for 3 digit ones

81*3=243, so there can't be any over 243.

2^2+81*2=166, so there can't be any 3-digit ones starting with 2

1^2+81*2=163, so there aren't any above that

so now you've only got to prove up to 163, which I suppose you could do on a case by case basis...

 

[hendon]

I think you have to show that for any n-digit number (where n>2), the number itself is much larger than the sum of the squares of the digits, so only 2-digit numbers are solutions.

say xyz is the number (in digits)
then sum of squares plus one = x^2 + y^2 + z^2 + 1

which is smaller than 100*x + 10*y + z
since y^2 + 1 < 10*y (since 0<=y<10)
and x^2 < 10*x (since 1<=x<10)
and z^2 < 90*x + z
(because 1<=x<=9 implies 90<=90*x<=810 implies z^2 < 90 <= 90x
implies z^2 < 90 <= 90x + z)

This can extend to n>3-digit numbers too...

you could then do some sort of proof for 2-digit numbers, or do the search as you have done to yield the 2 solutions...

 

[xtreme2k]

It is actually pretty tough problem but this is what I got out of it as the prove that if it is bigger than 99, it is impossible to have 1 as the difference...

say AB is the number from 0 - 99.
And we want to prove 10A + B - Asq - Bsq = 1 (Asq meaning A square)

Lets restrict for now
A in the range of 0=<A=<9 (meaning A can be 0 to 9 inclusive)
B in the range of 0=<B=<9 (meaning B can be 0 to 9 inclusive)

It can be seen that
if 0=<A=<9 and in 10A - Asq, the answers can ONLY be either 0,9,16,21,24,25
B <= Bsq if 0=<B=<9 and in B - Bsq, the answers for this can ONLY be either 0,-2,-6,-12,-20,-30,-42,-56,-72

Now we do 10A - Asq + (B -Bsq) = 1, the only 'combination' could be 21 - 20 = 1. Therefore POSSIBLE to happen in a 2 digit number. Proven that it will WORK in a 2 digit number.

Now we need to prove it also does NOt work for A > 10.
But this is easy. IF A >= 10
10A - Asq values can only be -11,-24,-39-,-56,-75 and continues to decrease
B - Bsq values, as above can only be 0,-2,-6,-12,-20,-30,-42,-56,-72
Therefore (10 - Asq) + (B - Bsq) cannot ever equal to 1 if (A >= 10)
Proved.

 

[Pretender]

Numbers over 244 shouldn't work (I haven't proven it, but I'm pretty sure), since
244 = 9^2 + 9^2 + 9^2 + 1 (i.e. the highest 3-digit number)
Since for 4 digit numbers, the sum of the digits squared would be less than 1000 (at least for the first few digits above 4), and much less than the actual number you have.

So all you need to do are look thru all the numbers from 1 to 244.
For 2-digit numbers, you can find all values of t and u in which
(t * t) + (u * u) + 1 = 10t+ u
And for 3 digits, you can just add in an 'h' (for hundreds place) to the right, and (h*h) to the left.

I may be wrong, since I'm only in precalc, but this seems pretty simple, especially with that program of yours.

 

[xtreme2k]

It basically doesnt work above 99.

Look at my prove.

 

[mulder]

Thanks for all the help! I'll read thru the posts in a little while. I have some other work I need to get done first. However, I can say that we all were on the right track. My friend and I started thinking and we looked at 4 digits. And the maximum sum of the digits when there are 4 is 324. Examine the table:

Digits -- Max Number -- Sum
---------------------------
4 -- 9999 -- 324
5 -- 99999 -- 405
6 -- 999999 -- 486
7 -- 9999999 -- 567
n -- (10^n) - 1 -- 81 * n

If you will see that after 4 digits the growth of the max number is exponential where the growth of the sum in linear; always growing by 81. I think for one way to prove it, we can find the derivatives of both functions and show that they never intersect after 2 digits. I say 2-digits, because there will be an intersection. That's where 35 and 75 are. When you start getting in to higher digits, there is no way for the sums to even attempt to get close to the value of the original number. But after that there is nothing.

Thanks again for the help. : ) I'll let you know how everything turns out. This has to be done in about 2 weeks.

 

[xtreme2k]

I duno, maybe I am biased to myself

But seriously my method of proving is yet so simple, but did everything you require.

 

[Mday]

here is a little number theory, the product of a sum of squares, is a sum of squares. all prime numbers in the form of 4n+1, where n is an integer, is also a sum of squares.

 

[Mday]

how can you prove that there are an infinite number of positive integers? NOTE: the number ZERO, 0, is not positive.

1. assume that there are a finite number of positive integers.
2. the integers have the property that they are &quot;well ordered&quot; meaning, you can put them in some order... say smallest to largest (you may have to prove that, but given x and y integers, you can tell which is larger)... you can resort to a &quot;sorting&quot; algorithm...
3. going with your assumption (finite number), it is possible to write out all the positive numbers which is complete...
4. since there is a way to pick the largest one, take that largest integer.
5. add 1 to that integer
6. you have come up with a number that is not on the list.
7. that means the original list was not complete.
8. contradiction, since the list was COMPLETE, there must be an infinite number of postive integers

 

[Pretender]

Congrats mday, you've proven that there are infinate positive integers. We've already proven that the highest possible solution is in the hundreds or less (99 as mentioned by xtreme), so the limitations of the integer set are irrelevant here.

 

[mulder]

xtreme,

I think that you are correct. I have gone back re-read the posts and there may be multiple ways to prove this problem, but I think yours is the easiest. I am going to study the solutions some more, because I will have to present the findings to the teacher. However, based upon everything I have read so far, it seems to work. Thanks for the help.

That thanks goes out to all the others too. I really appreciate it. Once again, I will post here with the teacher's comments. Hopefully it will be good news.

 

[xtreme2k]

Thanks

However, after re-reading my solution again, I found out there is a flaw in the last part of it. The assumption of A > 10 part is wrong. But the good thing is I can only prove it is POSSIBLe for 2 digit, there is no need to 'disprove' for 3 digit or 4 digit, etc.

 

[Suicidal]

Um, 6?

 

[mulder]

I have been talking with my roommate and I am going to try to incorporate the derivatives into the proof. Basically everyone here can agree that after 2 digits there is no solution. This can be easily shown with a graph. However, I cannot plot an infinite number of points to show the graph will never intersect way way down the line. That's where the derivatives will come into play.

Suicidal,

What do you mean by 6?

 

[xtreme2k]

I am looking at some Induction kinda prove from what I did before.