wu :: forums
« wu :: forums - An Onerous Fence »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 6:46am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   easy
(Moderators: william wu, Grimbal, SMQ, ThudnBlunder, Eigenray, towr, Icarus)
   An Onerous Fence
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: An Onerous Fence  (Read 50494 times)
rloginunix
Uberpuzzler
*****





   


Posts: 1026
An Onerous Fence  
« on: Oct 29th, 2016, 8:01am »
Quote Quote Modify 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: male
Posts: 500
Re: An Onerous Fence  
« Reply #1 on: Oct 29th, 2016, 1:00pm »
Quote Quote Modify 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 Quote Modify Modify

The zeroth (or negative oneth*, depending on your numbering system) term is an integer square, as is the term before it. Wink
 
*negative first?
IP Logged
rloginunix
Uberpuzzler
*****





   


Posts: 1026
Re: An Onerous Fence  
« Reply #3 on: Oct 31st, 2016, 8:50am »
Quote Quote Modify 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: male
Posts: 500
Re: An Onerous Fence  
« Reply #4 on: Oct 31st, 2016, 6:00pm »
Quote Quote Modify 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: male
Posts: 13730
Re: An Onerous Fence  
« Reply #5 on: Oct 31st, 2016, 11:18pm »
Quote Quote Modify 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 Tongue
« 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 Quote Modify 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
Re: An Onerous Fence   p8.png
« Reply #7 on: Nov 1st, 2016, 8:27am »
Quote Quote Modify Modify

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: male
Posts: 13730
Re: An Onerous Fence  
« Reply #8 on: Nov 1st, 2016, 9:57am »
Quote Quote Modify 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 Tongue
 
(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 Quote Modify Modify

You're right, I am not, Grin
 
 
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: male
Posts: 13730
Re: An Onerous Fence  
« Reply #10 on: Nov 2nd, 2016, 9:58am »
Quote Quote Modify 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. Tongue
 
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 Quote Modify 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 Quote Modify Modify

towr just stole someone else's thunder, Smiley
 
But - the (base-ten) number ...444 can be manipulated.
 
Hm, I wonder how.
IP Logged
pex
Uberpuzzler
*****





   


Gender: male
Posts: 880
Re: An Onerous Fence  
« Reply #13 on: Nov 2nd, 2016, 2:13pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 500
Re: An Onerous Fence  
« Reply #15 on: Nov 3rd, 2016, 7:09pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: An Onerous Fence  
« Reply #17 on: Nov 4th, 2016, 12:58am »
Quote Quote Modify 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: male
Posts: 500
Re: An Onerous Fence  
« Reply #18 on: Nov 4th, 2016, 12:15pm »
Quote Quote Modify 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 Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: An Onerous Fence  
« Reply #20 on: Nov 5th, 2016, 8:07am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: An Onerous Fence  
« Reply #22 on: Nov 6th, 2016, 8:22am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: An Onerous Fence  
« Reply #24 on: Nov 6th, 2016, 10:25pm »
Quote Quote Modify 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
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board