mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-02-04, 20:24   #56
SmartMersenne
 
Sep 2017

22·3·7 Posts
Default

Quote:
Originally Posted by DukeBG View Post
My solution is not listed, as far as I can tell. Though I didn't try to normalize the listed ones.

[0, 36295, 233415, 717255] & [93^2, 267^2, 501^2, 1059^2]
the second set expanded [8649, 71289, 251001, 1121481]

I also claim that this pair of sets is the 4-4 solution with the smallest possible largest element of the set with the zero. (Assuming both sets contain non-negative numbers, of course).
I believe, though don't claim, that it is also the smallest possible largest element of both sets.

My other 4-4 solution is [0, 259875, 475875, 1313091] & [15^2, 447^2, 895^2, 1695^2]. In case anyone wants to make a registry of normalized solutions.

I ended up not bothering to find 4-5 or larger solution.
[0, 62640, 242352, 1112832] & [8649, 44944, 242064, 725904]
SmartMersenne is offline   Reply With Quote
Old 2019-02-05, 09:57   #57
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

It seems to me that this problem should have a much easier solution than I have found. My code spends the majority of its time finding possible B2s and A3s(A1=0). I wish I could come up with an efficient way of finding all numbers of the form x^2-b1 and x^2-b2.
henryzz is offline   Reply With Quote
Old 2019-02-05, 13:02   #58
DukeBG
 
Mar 2018

12910 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
[0, 62640, 242352, 1112832] & [8649, 44944, 242064, 725904]
Thank you for shattering my belief. My claim still stands, though. Also, I now see a fault in some my calculations that made me ignore a lot of numbers. Sigh... Maybe I'll get back to this search by the end of the week.

Quote:
Originally Posted by uau View Post
I doubt anyone would bother with a list of 4+4 solutions, or at least not one maintained by hand. I found over two thousand different 4+5 solutions, and 4+4 ones are more common (I didn't directly count those). Currently found 4+6 solutions could be listed by hand, but 4+5 and smaller are too common for that.
Ahh... Ok, then.

Last fiddled with by DukeBG on 2019-02-05 at 13:05
DukeBG is offline   Reply With Quote
Old 2019-02-05, 17:11   #59
SmartMersenne
 
Sep 2017

22·3·7 Posts
Default

Quote:
Originally Posted by DukeBG View Post
Thank you for shattering my belief. My claim still stands, though. Also, I now see a fault in some my calculations that made me ignore a lot of numbers. Sigh... Maybe I'll get back to this search by the end of the week.

[0, 54432, 119392, 263872] & [324, 79524, 227529, 1258884]

Last fiddled with by SmartMersenne on 2019-02-05 at 17:19 Reason: Typo in third number of the second set. Fixed
SmartMersenne is offline   Reply With Quote
Old 2019-02-05, 18:27   #60
uau
 
Jan 2017

79 Posts
Default

Quote:
Originally Posted by DukeBG View Post
Thank you for shattering my belief
You realize his solution was the same as yours? Just adding a constant to one set and subtracting it from the other, which doesn't change the sums.
uau is offline   Reply With Quote
Old 2019-02-05, 18:41   #61
uau
 
Jan 2017

79 Posts
Default

Quote:
Originally Posted by henryzz View Post
It seems to me that this problem should have a much easier solution than I have found. My code spends the majority of its time finding possible B2s and A3s(A1=0). I wish I could come up with an efficient way of finding all numbers of the form x^2-b1 and x^2-b2.
I don't know what kind of approach exactly you used, but based on the results it seems nobody found a more efficient approach than mine. A basic idea behind it is that given a number D, you can find all possible integers x such that x2+D is a square. This means that if you know the difference between two members of one set, say (a2-a1)=D, then you can find a finite set containing all possible values of b+a1 for any member b of the other set (since b+a1 is a square, x2, and b+a2 = (b+a1) + (a2-a1) = x2+D).


If x2+D=y2, then D=y2-x2=(y-x)(y+x). If you generate all divisors k of D, then you can solve for possible values of x from (y-x)=k, (y+x)=D/k -> x = (D/k - k)/2.
uau is offline   Reply With Quote
Old 2019-02-05, 20:05   #62
DukeBG
 
Mar 2018

12910 Posts
Default

Quote:
Originally Posted by uau View Post
If you generate all divisors k of D, then you can solve for possible values of x from (y-x)=k, (y+x)=D/k -> x = (D/k - k)/2.
That's what I did too!

However I mistakenly ignored even D's. The (...)/2 part requires that the two divisors have the same evenness (oddity? translating math terms I'm used to into english is sometimes a pain), so 2 as a prime divisor cannot be in power 1. If present in D, it should be present in both sides of the "split" into two divisors. (My mistake was that I decided it shouldn't be present at all because the solutions with it on both sides could be simplified into a solution without it. Nevermind it, wrong conclusion)

Quote:
You realize his solution was the same as yours?
D'oh. That's why it looked familiar. I'm deeply ashamed of myself, that was obvious in the hindsight.

Raises the question of how to normalize these solutions then... Although that doesn't help in any way in finding bigger sets.
DukeBG is offline   Reply With Quote
Old 2019-02-06, 10:48   #63
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

I was calculating a list of x^2-b1 storing it and then reusing the filtered list when looking for a b2.
The thing I hadn't thought about was using difference of squares trick. I need to think on this further.

Using my current method I think can do an exhaustive search upto 1e9 in around 24 hours.
henryzz is offline   Reply With Quote
Old 2019-02-06, 12:55   #64
uau
 
Jan 2017

79 Posts
Default

Quote:
Originally Posted by henryzz View Post
Using my current method I think can do an exhaustive search upto 1e9 in around 24 hours.
Exhaustive search of what? You'll find all solutions that have what parameter under 1e9? All the numbers in both sets are below that?

Last fiddled with by uau on 2019-02-06 at 12:56
uau is offline   Reply With Quote
Old 2019-02-06, 14:26   #65
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

Quote:
Originally Posted by uau View Post
Exhaustive search of what? You'll find all solutions that have what parameter under 1e9? All the numbers in both sets are below that?
a1, a2 etc below 1e9. Thinking about it a5 and a6 can be any size in my code.
henryzz is offline   Reply With Quote
Old 2019-02-22, 13:04   #66
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

166416 Posts
Default

Only just noticed that all the 4,6 solutions at the end are wrong. 1899+1899 is not square.

@uau What were your search limits for this puzzle? Did you search for 5,5 solutions?
After pinching your difference of squares idea, I have just started a run where a1=0, b1 and a2 < 1e9 and everything else < 1e12
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
2019 Coding Challenge miroslavkures Number Theory Discussion Group 2 2018-12-27 08:59
January 2018 Xyzzy Puzzles 0 2018-01-02 03:09
January 2017 Xyzzy Puzzles 4 2017-02-22 21:34
January 2016 R. Gerbicz Puzzles 17 2016-02-04 17:00
January 2015 Xyzzy Puzzles 1 2015-02-02 17:17

All times are UTC. The time now is 04:09.

Thu Oct 22 04:09:55 UTC 2020 up 42 days, 1:20, 0 users, load averages: 1.78, 1.57, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.