wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> An Onerous Fence
        
(Message started by: rloginunix on Oct 29th, 2016, 8:01am)
Title: An Onerous Fence
Post by rloginunix on Oct 29th, 2016, 8:01am
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?
Title: Re: An Onerous Fence
Post by Michael Dagg on Oct 29th, 2016, 1:00pm
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.
Title: Re: An Onerous Fence
Post by dudiobugtron on Oct 29th, 2016, 2:27pm
The zeroth (or negative oneth*, depending on your numbering system) term is an integer square, as is the term before it. ;)

*negative first?
Title: Re: An Onerous Fence
Post by rloginunix on Oct 31st, 2016, 8:50am
For a well-defined problem the base of 10 should be assumed.

Also, I see something funny going on with the [hide]tens digit in the squares of potential candidates[/hide]:

112 = [hide]121[/hide]
192 = [hide]361[/hide]
212 = [hide]441[/hide]
292 = [hide]841[/hide]

But I am not sure, may be it's just me.
Title: Re: An Onerous Fence
Post by Michael Dagg on Oct 31st, 2016, 6:00pm
> 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.
Title: Re: An Onerous Fence
Post by towr on Oct 31st, 2016, 11:18pm

on 10/31/16 at 18:00:44, 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 :P
Title: Re: An Onerous Fence
Post by dudiobugtron on Nov 1st, 2016, 12:32am

on 10/31/16 at 18:00:44, 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 [hide]tens[/hide] place.  ie: the [hide]second digit[/hide] to the left of the decimal mark.
Title: Re: An Onerous Fence
Post by rloginunix on Nov 1st, 2016, 8:27am
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).
Title: Re: An Onerous Fence
Post by towr on Nov 1st, 2016, 9:57am

on 11/01/16 at 08:27:02, 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 :P

(10*a+1)^2 = 1+20a  (mod 100)
(10*a+9)^2 = 81+20a  (mod 100)

2a+8 and 2a are obviously even.
Title: Re: An Onerous Fence
Post by rloginunix on Nov 2nd, 2016, 7:24am
You're right, I am not, ;D


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
Title: Re: An Onerous Fence
Post by towr on Nov 2nd, 2016, 9:58am
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. :P

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
Title: Re: An Onerous Fence
Post by dudiobugtron on Nov 2nd, 2016, 11:14am
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...)
Title: Re: An Onerous Fence
Post by rloginunix on Nov 2nd, 2016, 12:23pm
towr just stole someone else's thunder, :)

But - the (base-ten) number ...444 can be manipulated.

Hm, I wonder how.
Title: Re: An Onerous Fence
Post by pex on Nov 2nd, 2016, 2:13pm
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...
Title: Re: An Onerous Fence
Post by rloginunix on Nov 3rd, 2016, 9:01am
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).
Title: Re: An Onerous Fence
Post by Michael Dagg on Nov 3rd, 2016, 7:09pm

on 11/03/16 at 09:01:50, 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.
Title: Re: An Onerous Fence
Post by dudiobugtron on Nov 3rd, 2016, 11:44pm

on 11/03/16 at 19:09:18, 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.
Title: Re: An Onerous Fence
Post by towr on Nov 4th, 2016, 12:58am
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!)
Title: Re: An Onerous Fence
Post by Michael Dagg on Nov 4th, 2016, 12:15pm
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.
Title: Re: An Onerous Fence
Post by rloginunix on Nov 4th, 2016, 9:46pm

on 11/04/16 at 00:58:36, 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 (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1436904300). 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]
Title: Re: An Onerous Fence
Post by rmsgrey on Nov 5th, 2016, 8:07am
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)
Title: Re: An Onerous Fence
Post by rloginunix on Nov 5th, 2016, 10:56am
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.
Title: Re: An Onerous Fence
Post by towr on Nov 6th, 2016, 8:22am
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*
Title: Re: An Onerous Fence
Post by rloginunix on Nov 6th, 2016, 9:03am
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.
Title: Re: An Onerous Fence
Post by towr on Nov 6th, 2016, 10:25pm
Huh. And even for sk k>2 (i.s.o. 2) only two other solutions are known.
Title: Re: An Onerous Fence
Post by SWF on Nov 7th, 2016, 5:28pm
How about (333...)*(333...) = 111...   There are no final digits, thus avoiding the mod 4 issue.  I guess that doesn't count.  :-(
Title: Re: An Onerous Fence
Post by rloginunix on Nov 9th, 2016, 6:45pm
I think I got it but let us see if we can destroy this.

Lemma.Let en be an arbitrary even number > 2. Then:
en2 = 0, 4 (mod 16)

(direct) Proof. A given even number is a product of 2 and either an even number 2q or an odd number 2q+1 where q = 1, 2, 3, ...

In the first case:
ene = 2*2q = 4q, q = 1, 2, 3, ...

ene2 = 16q2 = 0 (mod 16)

In the second case:
eno = 2*(2q + 1), q = 1, 2, 3, ...

eno2 = 4(4q2 + 4q + 1) = 16q2 + 16q + 4 = 16(q2 + q) + 4 = 4 (mod 16)

What was required to prove.

For all fours, proof by contradiction. By hypothesis, a number composed of nothing but all fours is an even square, the number 44 being the smallest one of interest:
44 = 40 + 4 = 16*2 + 8 + 4 = 16*2 + 12 = 12 (mod 16)

444 = 400 + 44 = 4*100 + 44 = 4*4*25 + 44 = 16*25 + 16*2 + 12 = 12 (mod 16)

4444 = 4000 + 400 + 44 = 16*250 + 16*25 + 16*2 + 12 = 12 (mod 16)

44444 = 40000 + ... = 12 (mod 16)

etc. Contradiction: 12 is neither 0 nor 4. Hence, a number composed of nothing but all fours, 44 being the smallest such number, can not be a perfect square.

(shoot)
Title: Re: An Onerous Fence
Post by rloginunix on Nov 12th, 2016, 9:42am
Then:
122 = 144

382 = 1444

Can this pattern be continued?
Title: Re: An Onerous Fence
Post by dudiobugtron on Nov 12th, 2016, 11:25am

on 11/12/16 at 09:42:31, rloginunix wrote:
Then:
122 = 144

382 = 1444

Can this pattern be continued?

My calculator says that the square root of 14444 is not an integer.
Title: Re: An Onerous Fence
Post by rloginunix on Nov 12th, 2016, 1:01pm
I was hoping for some deductions, :)

and then something like:

... the longest string of fours that can terminate a square ...
Title: Re: An Onerous Fence
Post by towr on Nov 12th, 2016, 1:23pm
So like what I said in reply #10? (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1477753297;start=0#10) ::)
Title: Re: An Onerous Fence
Post by rloginunix on Nov 12th, 2016, 1:46pm
Dangit ... the tread's getting too long (and I am getting too old).


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