Author |
Topic: An Onerous Fence (Read 50494 times) |
|
rloginunix
Uberpuzzler
Posts: 1026
|
|
An Onerous Fence
« on: Oct 29th, 2016, 8:01am » |
Quote Modify
|
An Onerous Fence Is there any hope that somewhere within the following sequence: 11, 111, 1111, 11111, 111111, ... a perfect square of an integer will eventually show up?
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: An Onerous Fence
« Reply #1 on: Oct 29th, 2016, 1:00pm » |
Quote Modify
|
Not in general. For base 10, integer squares are 0 or 1 modulo 4 and that can't happen here. However, there are such squares in other bases.
|
|
IP Logged |
Regards, Michael Dagg
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: An Onerous Fence
« Reply #2 on: Oct 29th, 2016, 2:27pm » |
Quote Modify
|
The zeroth (or negative oneth*, depending on your numbering system) term is an integer square, as is the term before it. *negative first?
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1026
|
|
Re: An Onerous Fence
« Reply #3 on: Oct 31st, 2016, 8:50am » |
Quote Modify
|
For a well-defined problem the base of 10 should be assumed. Also, I see something funny going on with the tens digit in the squares of potential candidates: 112 = 121 192 = 361 212 = 441 292 = 841 But I am not sure, may be it's just me.
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: An Onerous Fence
« Reply #4 on: Oct 31st, 2016, 6:00pm » |
Quote Modify
|
> For a well-defined problem the base of 10 should be assumed. That logic is untenable. Is it no less (or more) tenable to assume, say, base 3, for example, than 10, given your problem statement. In other words, assuming base 3 is just as well-defined. The Mayan civilization whose counting base was double ours would be disappointed to hear that their problems are not well-defined. An nth formula in base 10 for your sequence is s_n = (10^{n+1} - 1)/3^2 , n >= 1. To show that s_n can be a square, it is enough to show that 10^{n+1} - 1 is a square for some n. It is easier to show that it is never a square. Your observation that numbers with 1 or 9 in their tenths place upon squaring generate a 1 in the tenths place is no surprise, nor coincidence. It may seem surreal but it isn't.
|
« Last Edit: Oct 31st, 2016, 6:02pm by Michael Dagg » |
IP Logged |
Regards, Michael Dagg
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: An Onerous Fence
« Reply #5 on: Oct 31st, 2016, 11:18pm » |
Quote Modify
|
on Oct 31st, 2016, 6:00pm, Michael Dagg wrote:> For a well-defined problem the base of 10 should be assumed. That logic is untenable. Is it no less (or more) tenable to assume, say, base 3, for example, than 10, given your problem statement. In other words, assuming base 3 is just as well-defined. The Mayan civilization whose counting base was double ours would be disappointed to hear that their problems are not well-defined. |
| I'd say it's safe to assume that he meant that if another base isn't explicitly given, then for a problem to be well-defined/unambiguous it should be assumed to have the base in common use in the civilization that produced the puzzle. Which in our case is base 10. If he had said it was an ancient Mayan puzzle, then we should have assumed it was base 20, or base 60 for ancient Babylonian (if I'm not mistaken). And now it's just a matter of time before someone here poses such a puzzle
|
« Last Edit: Oct 31st, 2016, 11:25pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: An Onerous Fence
« Reply #6 on: Nov 1st, 2016, 12:32am » |
Quote Modify
|
on Oct 31st, 2016, 6:00pm, Michael Dagg wrote:Your observation that numbers with 1 or 9 in their tenths place upon squaring generate a 1 in the tenths place is no surprise, nor coincidence. It may seem surreal but it isn't. |
| I think you are talking abut the ones place. rloginunix was talking about the tens place. ie: the second digit to the left of the decimal mark.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1026
|
What towr said: "yroehT rebmuN yratnemelE", notruB .M divaD, Sixth Edition, University of New Hampshire, Chapter 2, Divisibility Theory in Integers, Section 2, The Division Algorithm, Problem 8, page 19. dudiobugtron is correct (the parity of the digit in question always seems to be even. Hm, I wonder why).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: An Onerous Fence
« Reply #8 on: Nov 1st, 2016, 9:57am » |
Quote Modify
|
on Nov 1st, 2016, 8:27am, rloginunix wrote:(the parity of the digit in question always seems to be even. Hm, I wonder why). |
| I hope you're not seriously wondering that (10*a+1)^2 = 1+20a (mod 100) (10*a+9)^2 = 81+20a (mod 100) 2a+8 and 2a are obviously even.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1026
|
|
Re: An Onerous Fence
« Reply #9 on: Nov 2nd, 2016, 7:24am » |
Quote Modify
|
You're right, I am not, Was provoking the audience into posting (and proving) an even stronger result: if, in base ten, (ten in base ten), a perfect square of an integer is recorded with two or more digits then that square contains at least two distinct digits
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: An Onerous Fence
« Reply #10 on: Nov 2nd, 2016, 9:58am » |
Quote Modify
|
By exhaustive search no (base-ten) square of 4 or more digits ends in the same 4 digits. And ones with less than 4 have at least 2 distinct digits. Just looking at the last 2 digits is almost enough, if it weren't for ...44 (...00 is obviously preceded by something non-zero), and then when you look at three-digits, there's ...444 ! Number theory's a bastard. http://www.smbc-comics.com/comic/the-horrors-of-math
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: An Onerous Fence
« Reply #11 on: Nov 2nd, 2016, 11:14am » |
Quote Modify
|
I think rloginunix's new puzzle is the same as proving the original result (for the sequence of ones) also holds for the sequence of each other digit, ie each sequence from: 22, 222, 2222,... up to: 99, 999, 9999,... (Perhaps each puzzle could have a different name - "A Tworous Fence", etc...)
|
« Last Edit: Nov 2nd, 2016, 11:16am by dudiobugtron » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1026
|
|
Re: An Onerous Fence
« Reply #12 on: Nov 2nd, 2016, 12:23pm » |
Quote Modify
|
towr just stole someone else's thunder, But - the (base-ten) number ...444 can be manipulated. Hm, I wonder how.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: An Onerous Fence
« Reply #13 on: Nov 2nd, 2016, 2:13pm » |
Quote Modify
|
If an all-fours number would be a square, it would be an even square, so dividing it by four should still leave a square...
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1026
|
|
Re: An Onerous Fence
« Reply #14 on: Nov 3rd, 2016, 9:01am » |
Quote Modify
|
I was thinking along these lines. A perfect square can only end with 0, 1, 4, 5, 6, 9. A square of all zeros does not make much sense so, conversely, when it does - it has at least two distinct digits. The parity of the tens' digit of a square that ends with a 6 must be odd, otherwise - even. Therefore the digits of a perfect square can not be all the same unless they are all fours. A number that consists of nothing but all fours can be rewritten as, say, 44 = 4x11, 444 = 4x111, 4444 = 4x1111, etc. But we already proved that a number consisting of all ones can not be a perfect square (in base ten).
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: An Onerous Fence
« Reply #15 on: Nov 3rd, 2016, 7:09pm » |
Quote Modify
|
on Nov 3rd, 2016, 9:01am, rloginunix wrote:A number that consists of nothing but all fours can be rewritten as, say, 44 = 4x11, 444 = 4x111, 4444 = 4x1111, etc. But we already proved that a number consisting of all ones can not be a perfect square (in base ten). |
| I am not seeing the proof as you mentioned. My remarks fall short of a proof and in order to proceed as I suggested requires two facts to be proved -- namely that integer squares are 0 or 1 modulo 4, and that 10^{n+1} - 1, n>=1 is never 0 or 1 mod 4. There are other formulas for your sequence, some not too friendly, that will allow you to establish the same result but requires the exclusion of index. One needs to be a bit careful in working with the 4's sequence in this same way since 4 * s_n is always 0 mod 4. So that approach won't work.
|
|
IP Logged |
Regards, Michael Dagg
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: An Onerous Fence
« Reply #16 on: Nov 3rd, 2016, 11:44pm » |
Quote Modify
|
on Nov 3rd, 2016, 7:09pm, Michael Dagg wrote: I am not seeing the proof as you mentioned. My remarks fall short of a proof and in order to proceed as I suggested requires two facts to be proved -- namely that integer squares are 0 or 1 modulo 4, and that 10^{n+1} - 1, n>=1 is never 0 or 1 mod 4. |
| I thought your remarks were meant in a "proof is left to the reader as an exercise" kind of way. I thought this because proving that integer squares are always 0 or 1 modulo 4 is pretty easy once you realise to think of it in the first place. (Just square a generic even number and a generic odd number and it comes out of that.) Proving that a term of the sequence is not 0 or 1 modulo 4 is also not that 'onerous', since 100 is a multiple of 4. All terms of the sequence are 11 more than a factor of 100, so all of them are basically just 11 (ie: 3) modulo 4. Quote:One needs to be a bit careful in working with the 4's sequence in this same way since 4 * s_n is always 0 mod 4. So that approach won't work. |
| If a sequence is all 4s, then obviously 4 is a factor. This means that if it is a square, 2 is a factor of the square. So if some term of the 4s sequence was a square, you could take a factor of 2 out of the square root and still have an integer. Square that number, and you and get a term of the 1s sequence. Which is a contradiction.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: An Onerous Fence
« Reply #17 on: Nov 4th, 2016, 12:58am » |
Quote Modify
|
All 3s or all 7s is 1 mod 4, though. And you can't just divide out the factor 3 or 7 because they're not square. Of course a perfect square can't end in 3 or 7, so you can eliminate them by that route. Let's cover a few more bases, Say, b = 4k+2 all-1s in base b is sum(b^n for n>=0) = b+1 = 3 (mod 4) So these bases won't have an all 1s number > 1. Say, b = k^2+1 all-1s in base b is (b^{n+1}-1)/(b-1) which is square iff b^{n+1}-1 is square (because b-1 is square we can divide it out) But then we'd have two consecutive powers >1, which can only happen for 2^3 and 3^2, i.e. if k=1. And we already excluded b=2 previously. (Maybe using Catalan's conjecture / Mihailescu's theorem is a bit heavy-handed, if you have anything simpler, share!)
|
« Last Edit: Nov 4th, 2016, 1:03am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: An Onerous Fence
« Reply #18 on: Nov 4th, 2016, 12:15pm » |
Quote Modify
|
Mihailescu result is definite hammer. Cassel , WJ LeVeque among others studied a^x - b^y = 1. LeVeque circa 1950 is a simpler result. You should be able read it free at JSTOR. There is recent result regarding the Diophantine inequality 0 < |a^x - b^y| < max{a^{x/2}, b^{y/2}}/4 that is sharper, that is, if sharpness is of any relevance here. Off the top of my head I don't recall the author.
|
« Last Edit: Nov 4th, 2016, 3:20pm by Michael Dagg » |
IP Logged |
Regards, Michael Dagg
|
|
|
rloginunix
Uberpuzzler
Posts: 1026
|
|
Re: An Onerous Fence
« Reply #19 on: Nov 4th, 2016, 9:46pm » |
Quote Modify
|
on Nov 4th, 2016, 12:58am, towr wrote:(Maybe using Catalan's conjecture / Mihailescu's theorem is a bit heavy-handed, if you have anything simpler, share!) |
| 1) towr, you and I, we already went through the similar (base ten) exercise in 2015 in the Sum Of Consecutive Integers. Over there we dealt with a sum of consecutive integers while here we are dealing with the sum of tens whose powers are consecutive integers. 2) Proof by contradiction. (this was hinted at in Reply #3) In base ten for a square to end with a 1, the generating integer s must end with a 1 or the generating integer s must end with a 9 (the proof is left to the reader). 3) s ending in a 1 case: s = 1 + 101*p1 + 102*p2 + 103*p3 + ... + 10n*pn (1) Starting from the second term in (1) factor out 10: s = 1 + 10*(p1 + 101*p2 + 102*p3 + ... + 10n-1*pn) s+ = 1 + 10*q = 10*q + 1 for some q > 0. s ending in a 9 case: s = 9 + 101*p1 + 102*p2 + 103*p3 + ... + 10n*pn (2) We observe that: 9 = 10 - 1 (3) Put (3) into (2) (the -1 is all the way at the end): s = 10 + 101*p1 + 102*p2 + 103*p3 + ... + 10n*pn - 1(4) In all the terms but the last one in (4) factor out 10: s = 10*(1 + p1 + 101*p2 + 102*p3 + ... + 10n-1*pn) - 1 s_ = 10*q - 1 for some (other) q > 0. 4) In either case, s, by hypothesis, must be a square equal to the sum of consecutive powers of 10, k > 0: s2+ = (10*q + 1)2 = 1 + 101 + 102 + 103 + ... + 10k Raise the (10*q + 1) term to the second power: 100*q2 + 20*q + 1 = 1 + 101 + 102 + 103 + ... + 10k Cancel out the 1s on both sides of the above equation: 100*q2 + 20*q = 101 + 102 + 103 + ... + 10k Divide both sides of the above equation by 10: 10*q2 + 2*q = 1 + 101 + 102 + ... + 10k-1 On the left hand side of the above equation we have an integer whose parity is even while on the right hand side of the above equation we have an integer whose parity is odd: 2*(5*q2 + q) = 1 + 2*(5 + 5*101 + ... + 5*10k-2) Contradiction. Now, quicker, for s sub minus: 2*(5*q2 - q) = 1 + 2*(5 + 5*101 + ... + 5*10k-2) Contradiction. Hence, the original assumption that (in base ten) a number composed of all 1s can be a perfect square is faulty - it can not. [e] augmented as per rmsgrey's comments, see below. [/e]
|
« Last Edit: Nov 5th, 2016, 9:56am by rloginunix » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: An Onerous Fence
« Reply #20 on: Nov 5th, 2016, 8:07am » |
Quote Modify
|
There's a small hole in your proof - a special case: k=0 s+=s+=1 (one of those s+ is the root; the other is the square - you appear to be using the same symbol for both quantities)
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1026
|
|
Re: An Onerous Fence
« Reply #21 on: Nov 5th, 2016, 10:56am » |
Quote Modify
|
Aaaaa, the fence is onerous. Thank you for reading through this. Was typing late last night, way past my normal bed time. Square/root typo fixed. Since the sequence starts with "11", it is easiest to explicitly exclude the k=0 case by requiring that k,q > 0, see above. If we were to roll the sequence from "1", then we would have to augment all the relevant statements with "... except for the first term of 1, since 1x1=1". Some of my failures. A square must have an odd number of divisors. The proof is easy. If a divides n then b = n/a also divides n so divisors come in pairs. The only case when the distinction between a and b disappears is when a == b meaning a2 = n. Can we prove that the parity of the value of the tau function of an arbitrary fence number can never be odd? Enter prime factorization. The parity of all the powers of all the prime factors of a square must be even. Looking at the PF of the fence numbers we see that that never happens for known PFs. The first (and only) square creeps in at n = 9 (nine ones): 111,111,111 = 32 x 37 x 333667 The second time it happens is for n = 18: 111,111,111,111,111,111 = 32 x 7 x 11 x 13 x 19 x 37 x 52579 x 333667 Gut feeling and rigorous proof are uneasy friends. Turns out that in the late 1700s in Switzerland Johann III Bernoulli (careful now, the Roman numerals are important) had a weird hobby - computing the PFs of the fence numbers. In 1773 in the papers of Academy of Berlin he published a table for such PFs for 2 <= n <= 31 (n=2 means 11). He did not find the PF for n=11,17,29; he did not finish n=20,25,27; he made a few mistakes for n=22,24,26. In any case, nowadays these PFs are known to a rather large n and it would be a kick in the pants to prove that the above observation about the parity of the powers of prime factors of the fence numbers does not hold.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: An Onerous Fence
« Reply #22 on: Nov 6th, 2016, 8:22am » |
Quote Modify
|
At the point of my last comment, I think the #10 horse was already sufficiently dead and beaten. Which was why I was considering other horses, I mean, bases. (That they both also cover ten was a coincidence more than anything else.) What I'm wondering, among other bases, is there such an all-ones number other than 11 in base b={n^2-1} Because those are the only ones I can find. nvrmnd*: 111113 , 11117 Still rare, though. *) Funny that in python if you forget the word range, a for-loop like for n in (1,1000) will still work and do something. *grmbl*
|
« Last Edit: Nov 6th, 2016, 8:49am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1026
|
|
Re: An Onerous Fence
« Reply #23 on: Nov 6th, 2016, 9:03am » |
Quote Modify
|
To the best of my knowledge the answer is "what you typed is it" - Nagell-Ljunggren equation: (bn -1)/(b - 1) = s2 for n > 2 has exactly and only two solutions: n = 4 (b = 7) and n = 5 (b = 3). Which implies that in no base > 5 no fence number is a perfect square. Sucks.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: An Onerous Fence
« Reply #24 on: Nov 6th, 2016, 10:25pm » |
Quote Modify
|
Huh. And even for sk k>2 (i.s.o. 2) only two other solutions are known.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|