mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   January 2019 (https://www.mersenneforum.org/showthread.php?t=23947)

Xyzzy 2018-12-30 14:09

January 2019
 
[url]http://www.research.ibm.com/haifa/ponderthis/challenges/January2019.html[/url]

science_man_88 2018-12-30 14:48

[QUOTE=Xyzzy;504358][url]http://www.research.ibm.com/haifa/ponderthis/challenges/January2019.html[/url][/QUOTE]

I understand why the original numbers work but I don't see too much in the way of extending the problem. edit: okay I see one flaw with the original numbers.

a1call 2018-12-30 17:47

Here we go again with empty sets and semi empty sets.
Different conventions, conflictingly different solutions.
Makes the challenge flawed in my opinion.

Are primes products of distinct primes?
I would say not, but know of Wikipedia worshippers which would disagree.

science_man_88 2018-12-30 17:58

[QUOTE=a1call;504390]Here we go again with empty sets and semi empty sets.
Different conventions, conflictingly different solutions.
Makes the challenge flawed in my opinion.

Are primes products of distinct primes?
I would say not, but know of Wikipedia worshippers which would disagree.[/QUOTE]

take the individual sums if you look at them you'll find your answer.

a1call 2018-12-30 18:14

[QUOTE=science_man_88;504392]take the individual sums if you look at them you'll find your answer.[/QUOTE]

I disagree.

If Primes are [B]products [/B]of distinct primes then:

4 > 2 > 1
25 > 5 > 1
100 > 20 > 4 > 2 > 1
121 > 11 > 1

Bob wins.

Else if Primes [U]are-not[/U] [B]products [/B]of distinct primes then:

4, 25 and 121 have no winners so Alice will have the only choice of choosing 100 and then:

100 > 10 > 1

Bob wins.:smile:

science_man_88 2018-12-30 18:59

[QUOTE=a1call;504393]I disagree.

If Primes are [B]products [/B]of distinct primes then:

4 > 2 > 1
25 > 5 > 1
100 > 20 > 4 > 2 > 1
121 > 11 > 1

Bob wins.

Else if Primes [U]are-not[/U] [B]products [/B]of distinct primes then:

4, 25 and 121 have no winners so Alice will have the only choice of choosing 100 and then:

100 > 10 > 1

Bob wins.:smile:[/QUOTE]

false if the sum is a prime square, the only way not to repeat primes is for Alice to take the sqrt and Bob to divide by the sqrt a second time.

a1call 2018-12-30 19:19

[QUOTE=science_man_88;504398]false if the sum is a prime square, the only way not to repeat primes is for Alice to take the sqrt and Bob to divide by the sqrt a second time.[/QUOTE]
What exactly are you referring to when you say false?
Please be more specific. Thanks.

science_man_88 2018-12-30 19:25

[QUOTE=a1call;504402]What exactly are you referring to when you say false?
Please be more specific. Thanks.[/QUOTE]

you're just arguing that because you can assume a bunch of cases don't work that it's ambiguous. it's not. you can complain to the puzzlemaster you know.

a1call 2018-12-30 19:29

[QUOTE=science_man_88;504405]you're just arguing that because you can assume a bunch of cases don't work that it's ambiguous. it's not. you can complain to the puzzlemaster you know.[/QUOTE]

I am saying that two different conventions will both work and that's why the challenge is vague.
And frankly I don't need you to let me know if I can or can not raise the issue with anyone.

science_man_88 2018-12-30 19:38

[QUOTE=a1call;504407]I am saying that two different conventions will both work and that's why the challenge is vague.
And frankly I don't need you to let me know if I can or can not raise the issue with anyone.[/QUOTE]

many different conventions work in code as well, you don't complain about that. my point is if you want it to be unvague you can get an explanation from the puzzlemaster not here.

SmartMersenne 2018-12-30 23:41

[QUOTE=a1call;504390]Here we go again with empty sets and semi empty sets.
Different conventions, conflictingly different solutions.
Makes the challenge flawed in my opinion.

Are primes products of distinct primes?
I would say not, but know of Wikipedia worshippers which would disagree.[/QUOTE]

1 is NOT a prime by definition. The smallest prime is 2.

So primes are NOT a product of distinct primes, because a product is defined by at least 2 terms.

a1call 2018-12-31 00:02

[QUOTE=SmartMersenne;504432]1 is NOT a prime by definition. The smallest prime is 2.

So primes are NOT a product of distinct primes, because a product is defined by at least 2 terms.[/QUOTE]

I agree with you, but like I said there are those who consider a product with no factors a valid function just because the infallible Wikipedia has an article about it::smile:

[url]https://en.wikipedia.org/wiki/Empty_product[/url]

SmartMersenne 2018-12-31 00:10

[QUOTE=a1call;504434]I agree with you, but like I said there are those who consider a product with no factors a valid function just because the infallible Wikipedia has an article about it::smile:

[url]https://en.wikipedia.org/wiki/Empty_product[/url][/QUOTE]

[URL="https://www.google.com/search?ei=qlgpXIf_Fr7L0PEP0JGEmAo&q=if+it%27s+on+the+internet+it+must+be+true+meme&oq=+%22If+it+is+on+the+internet%2C+it+must+be+true%22&gs_l=psy-ab.1.1.0i22i30l5.1330891.1330891..1339030...0.0..0.97.97.1......0....1j2..gws-wiz.......0i71.VVRWKY99BK4"]"If it is on the internet, it must be true"[/URL] :smile:

Yes but we are talking about at least one term here.

a1call 2018-12-31 00:38

[QUOTE=SmartMersenne;504435][URL="https://www.google.com/search?ei=qlgpXIf_Fr7L0PEP0JGEmAo&q=if+it%27s+on+the+internet+it+must+be+true+meme&oq=+%22If+it+is+on+the+internet%2C+it+must+be+true%22&gs_l=psy-ab.1.1.0i22i30l5.1330891.1330891..1339030...0.0..0.97.97.1......0....1j2..gws-wiz.......0i71.VVRWKY99BK4"]"If it is on the internet, it must be true"[/URL] :smile:

Yes but we are talking about at least one term here.[/QUOTE]
It is not much of a stretch to go from a product with no factors being a valid function to one with one factor being valid as well.
Please see post number 6 above.
Regardless of if we accept the convention to be valid or not, the ambiguity of the challenge at not clarifying the concept of product-of-distinct-prime makes the challenge problematic.
We are left to guessing what the "Puzzle-Master" considers a valid convention.

Dr Sardonicus 2018-12-31 01:54

Between the example and the requirement that a play actually does something, there seems to be no difficulty understanding which divisors are allowed. It could have been stated more precisely, but the cavils of the willfully obtuse are probably not a major concern of the folks writing these problems.

There does however appear to be a grammatical oopsadaisy. I believe the last comma in the statement of the problem is misplaced. It should be moved one word to the right, from after "numbers" to after "each."

a1call 2018-12-31 02:08

[QUOTE=Dr Sardonicus;504442]Between the example and the requirement that a play actually does something, there seems to be no difficulty understanding which divisors are allowed. It could have been stated more precisely, but the cavils of the willfully obtuse are probably not a major concern of the folks writing these problems.

There does however appear to be a grammatical oopsadaisy. I believe the last comma in the statement of the problem is misplaced. It should be moved one word to the right, from after "numbers" to after "each."[/QUOTE]

Right, some of us are just glass is Half-Full type of people by nature. Aren't we now?

:blahblah:

SmartMersenne 2018-12-31 02:21

[QUOTE=a1call;504437]It is not much of a stretch to go from a product with no factors being a valid function to one with one factor being valid as well.
Please see post number 6 above.
Regardless of if we accept the convention to be valid or not, the ambiguity of the challenge at not clarifying the concept of product-of-distinct-prime makes the challenge problematic.
We are left to guessing what the "Puzzle-Master" considers a valid convention.[/QUOTE]

The solution won't change in either case. Players can use a single prime.

In the case of allowing a product with no terms: that would get the game into an infinite loop. And if people can't see it, their program will get into an infinite loop, so I would like to see how they will solve it. :smile:

Dr Sardonicus 2018-12-31 15:29

The set B in the example (but not the set A) can easily be expanded to four positive integers. Not that this is of any use in solving the problem, of course...

SmartMersenne 2018-12-31 22:08

[QUOTE=Dr Sardonicus;504471]The set B in the example (but not the set A) can easily be expanded to four positive integers. Not that this is of any use in solving the problem, of course...[/QUOTE]

Care to elaborate?

science_man_88 2019-01-01 03:33

[QUOTE=Dr Sardonicus;504471]The set B in the example (but not the set A) can easily be expanded to four positive integers. Not that this is of any use in solving the problem, of course...[/QUOTE]

neither does the fact that all sums must not be squarefree. BTW a1call here's the puzzlemasters reply:

[QUOTE]I meant one or more primes; will update the site. [/QUOTE]

Dr Sardonicus 2019-01-01 15:03

[QUOTE=SmartMersenne;504538][QUOTE=Dr Sardonicus;504471]The set B in the example (but not the set A) can easily be expanded to four positive integers. Not that this is of any use in solving the problem, of course...[/QUOTE]
Care to elaborate?[/QUOTE]
A = {3,99}, B = (1,22,97,526}

a1call 2019-01-01 17:59

It is quite an interesting challenge.
I have tens of glasses which are 15/16 full but I am quite peptomestic about filling the last 1/16 of any of them.:smile:
One interesting aspect is that the square root of the sums seem to form in interesting and different patterns.
Many are symmetrical around a 45° diagonal.
Others form a row of primes then primesx2 then semi-primes then semi-primesx2 and other patterns as well.
And of course my posts would not be complete without a few painfully annoying nags to some:
The challenge does not define any rules regarding repeating terms within/between the two sets A & B. Without such clarifications many trivial solutions can be found.

SmartMersenne 2019-01-01 23:33

[QUOTE=a1call;504604]It is quite an interesting challenge.
I have tens of glasses which are 15/16 full but I am quite peptomestic about filling the last 1/16 of any of them.:smile:
One interesting aspect is that the square root of the sums seem to form in interesting and different patterns.
Many are symmetrical around a 45° diagonal.
Others form a row of primes then primesx2 then semi-primes then semi-primesx2 and other patterns as well.
And of course my posts would not be complete without a few painfully annoying nags to some:
The challenge does not define any rules regarding repeating terms within/between the two sets A & B. Without such clarifications many trivial solutions can be found.[/QUOTE]

Yup: A=[3, 99, 3, 99] B=[1, 22, 1, 22]

Dr Sardonicus 2019-01-02 00:46

[QUOTE=SmartMersenne;504630]Yup: A=[3, 99, 3, 99] B=[1, 22, 1, 22][/QUOTE]
AFAIK there is no such thing as repetition of elements in a [i]set[/i]. A set is not the same thing as an ordered tuple.

The two sets need not be disjoint, however. Clearly, adding a number to all the elements of one set, and subtracting it from all the elements of the other, creates two sets giving the same sums. So instead of [1,22] and [3,99] we could take [2,23] and [2,98].

a1call 2019-01-02 00:58

[QUOTE]
In mathematics, a set is a collection of distinct objects,
[/QUOTE]

[url]https://en.wikipedia.org/wiki/Set_(mathematics[/url])

Thank you for the correction.:smile:

science_man_88 2019-01-02 01:08

[QUOTE=Dr Sardonicus;504636]AFAIK there is no such thing as repetition of elements in a [i]set[/i]. A set is not the same thing as an ordered tuple.

The two sets need not be disjoint, however. Clearly, adding a number to all the elements of one set, and subtracting it from all the elements of the other, creates two sets giving the same sums. So instead of [1,22] and [3,99] we could take [2,23] and [2,98].[/QUOTE]

multiset is the term for an object like a set, but with multiplicities. the sums need all be squares, and since squares are 0 or 1 mod 4 , any term in A that is 2 mod 4 forces the elements of B to all be 2 or 3 mod 4. presence of an element that is 1 mod 4 forces the opposite set to all be 0 or 3 mod 4. 3 mod 4 forces all elements of the opposite set to be 1 or 2 mod 4. and 0 mod 4 forces 0 or 1 mod 4. mod 9 all squares are 0,1,4, or 7. etc. anyways time to use forpart ( or setbinop etc doh )and forsubset to try my hand at coding it.

Kebbaj 2019-01-03 18:58

triplet with a pair
 
Until now, i only have a triplet with a pair :

A = {22, 97, 526}; B = {3, 99};

22 + 3 = 25 Factor {{5^2}}

22 + 99 = 121 Factor {{11^2}}

97 + 3 = 100 Factor {{2^2},{5^2}}

97 + 99 = 196 Factor {{2^2},{7^2}}

526 + 3 = 529 Factor {{23^2}}

526 + 99 = 625 Factor {{5^4}}

Kebbaj 2019-01-03 19:31

it is going well
 
it is going well: quadriplet with pair:

B = {3, 99, 4803, 45699} ; A = {97, 526};

LaurV 2019-01-04 05:57

[QUOTE=a1call;504402]What exactly are you referring to when you say false?
Please be more specific. Thanks.[/QUOTE]
He refers to the fact that if you don't have the restriction of distinct primes, then Alice (the first choicer) wins every time by dividing with the number itself.

25 -> 1
100 -> 1
etc.

This problem has not much to program, is pure math, and quite simple actually.[SPOILER] As said above, N must always be a perfect square. The sums can not be square free, because Alice would win in one shot, picking the whole number as the first divisor, and they can't be non-squares, because then Alice will chose the first time in such a way to leave a perfect square, and she wins. For example, if \(N=2^a3^b5^c...\) then Alice picks first time the product of all primes which have the odd power, and then what is left is a perfect square. Now, the only left for you is to prove that if the number is perfect square, then Bob (the second picker) wins every time. There is a theorem which states that the only numbers with an odd number of divisors are the perfect squares (why? and why do you need an odd number of divisors?) anyhow this is not complicate to prove, but you don't need to go so deep, because there is a simple strategy to win: if N is perfect square, then any prime in N has its pair, and all Bob has to do is to pick the same product Alice picks, every time, leaving every time behind a perfect square. Start with a perfect square, end with a smaller perfect square, repeat. This ends in 1, and it is the "infinite descent" method, invented by Fermat, hehe - as members of mersenneforum, you should know that :razz:

So, all the fuss is about finding two sets of numbers whose paired sums are always perfect squares. How difficult is that? (from the number of the persons who already solved the puzzle in just few hours, and from this current thread, you can see that the puzzle is trivial - so this is another skip this month).[/SPOILER]

a1call 2019-01-04 06:38

And how does any of that have to do with the text that he quoted from me and labeled as false?
Where is exactly the error in my post?
Please make a direct reference to the false statement.
Thanks.

LaurV 2019-01-04 07:17

[QUOTE=a1call;504390]Are primes products of distinct primes?
I would say not, but know of Wikipedia worshippers which would disagree.[/QUOTE]

Your posts are generally just bullshit, insinuations, insulting the intelligence of the audience, and blah blah blah, so I do not read them in detail anymore, for long time. Generally, primes are primes, can not be composite (i.e. product of primes), and well, even if you reformulated in the next post, to use Title case, which makes more sense (as the "set" of divisors, but is is still extremely odd to call them Primes, as they are mostly composite). However, we can satisfy you this time, with the exact stupidity that you say:

[QUOTE=a1call;504393]
Else if Primes [U]are-not[/U] [B]products [/B]of distinct primes then:
4, 25 and 121[COLOR=Red] have no winners[/COLOR][/QUOTE]

Oh? How come? I just said how Alice wins in this case...

axn 2019-01-04 07:42

[QUOTE=LaurV;504877]Oh? How come? I just said how Alice wins in this case...[/QUOTE]

As I understand it, the sticking point for a1call is the "[B]product[/B] of distinct primes" bit. According to him, a single prime is not a product -- there should be at least two.

EDIT:- Looks like they have updated "divides N by any divisor that is either a prime or a product of distinct prime numbers". That should take care of that.

science_man_88 2019-01-04 09:49

[QUOTE=axn;504884]EDIT:- Looks like they have updated "divides N by any divisor that is either a prime or a product of distinct prime numbers". That should take care of that.[/QUOTE]

yeah I contacted the puzzlemaster and posted the response in this thread.

science_man_88 2019-01-05 12:46

here's another thing you all may have noticed neither A or B can have more than 2 values mod 4 within them.

henryzz 2019-01-05 17:06

Have found plenty of 4+3 solutions but no 4+4 yet. Not sure I can search much further

henryzz 2019-01-07 09:57

[QUOTE=henryzz;505034]Have found plenty of 4+3 solutions but no 4+4 yet. Not sure I can search much further[/QUOTE]

Turns out I had a bug. 4+4 solutions found.

Something I hadn't realized is that if A=[a,b,c,d] and B=[e,f,g,h] is a solution then A=[a-1,b-1,c-1,d-1] and B=[e+1,f+1,g+1,h+1] is a solution. I think this means that you can set a=1 and generate all solutions based on this.

axn 2019-01-07 10:44

[QUOTE=henryzz;505189]I think this means that you can set a=1 and generate all solutions based on this.[/QUOTE]
Or set a=0. This way, all the entries in the other set will be squares.

henryzz 2019-01-07 12:47

Unfortunately I have found a bug that invalidates my solutions.

@axn that is potentially a useful idea.

Dieter 2019-01-13 07:46

[FONT=Calibri][SIZE=3]Eight days ago, I have found a 4+4 solution and a few hours later a 4+5 solution - sufficient for a "*". But the search for a 4+6 solution - [a1,a2,a3,a4] and [b1,b2,b3,b4,b5,b6] with ai+bj = square number [/SIZE][SIZE=3]– [/SIZE][SIZE=3]seems to be difficult. Until now I have only three “quasi-solutions” with 23 of 24 fulfilled conditions: [/SIZE][/FONT]
[FONT=Calibri][SIZE=3]cij: = ai +bj = a square number is correct [/SIZE][SIZE=3]for i = 1 to 4 and j = 1 to 6; only [/SIZE][/FONT]
[FONT=Calibri][SIZE=3]a4 + b6 is no square number. [/SIZE][/FONT]
[SIZE=3][FONT=Calibri]I would like to know which sort of solutions other people with “*” have sent to the puzzle master. [/FONT][/SIZE]

uau 2019-01-13 17:04

[QUOTE=Dieter;505742][SIZE=3][FONT=Calibri]I would like to know which sort of solutions other people with “*” have sent to the puzzle master. [/FONT][/SIZE][/QUOTE]
I've found a 4+6 solution.

petrw1 2019-01-13 20:20

The age old binary question: 1 or 0
 
Just curious if you are having more luck if a1=1 or a1=0?
I found a (4,3) solution quite easily with a1=1.

I guess the third option could be: a1 != {0,1}

Dieter 2019-01-14 07:50

[QUOTE=petrw1;505800]Just curious if you are having more luck if a1=1 or a1=0?
I found a (4,3) solution quite easily with a1=1.


That's no question for me, because I don't use ai and bj as parameters. My parameters for the search are the square numbers cij = ai + bj.


I don't know, if I am allowed to write more here.

henryzz 2019-01-14 11:44

[QUOTE=petrw1;505800]Just curious if you are having more luck if a1=1 or a1=0?
I found a (4,3) solution quite easily with a1=1.

I guess the third option could be: a1 != {0,1}[/QUOTE]

The value for a1 shouldn't make a difference. If you add 1 onto all As and subtract 1 from all Bs then you have a new solution. As such something needs to be fixed. This can be 0 or 1.

petrw1 2019-01-14 16:03

[QUOTE=henryzz;505860]The value for a1 shouldn't make a difference. If you add 1 onto all As and subtract 1 from all Bs then you have a new solution. As such something needs to be fixed. This can be 0 or 1.[/QUOTE]

Good point .... or if you have a 4X4 solution put a zero in one list.

Dieter 2019-01-18 13:57

4-6-solution
 
Having finally found a 4-6-solution I would like to know, if anyone has found a 4-7-solution.

petrw1 2019-01-18 14:37

How about a 5x5?
Not me.

henryzz 2019-01-18 22:51

If ai+b is a square and aj-ai>0 is less than 2*sqrt(ai+b)+1 then aj+b can't be a square as it is less than the next square (sqrt(ai+b)+1)^2

uau 2019-01-26 17:40

I improved my search program a bit and have found 8 distinct 4+6 solutions. Looks like 4+7 or 5+5 solutions would have to be pretty huge. It's not obvious whether arbitrarily large solutions can be expected to exist at all. Has anyone tried to analyze that?

Dieter 2019-01-27 06:06

3-13
 
[QUOTE=uau;506908]I improved my search program a bit and have found 8 distinct 4+6 solutions. Looks like 4+7 or 5+5 solutions would have to be pretty huge. It's not obvious whether arbitrarily large solutions can be expected to exist at all. Has anyone tried to analyze that?[/QUOTE]

Using your approach I have found a 3-13-solution - but I fear that this doesn‘t help very much. I continue to search for 4+7, but without analyzing.

henryzz 2019-01-27 10:59

Given all the differences between squares need lots of factors I would expect solutions to get bigger and bigger as more factors are needed.

Xyzzy 2019-02-03 13:43

[url]http://www.research.ibm.com/haifa/ponderthis/solutions/January2019.html[/url]

uau 2019-02-03 14:01

[QUOTE=Xyzzy;507545][URL]http://www.research.ibm.com/haifa/ponderthis/solutions/January2019.html[/URL][/QUOTE]

This lists the same 4+6 solution many times as a "different" one. If you multiply all the numbers by a second power, all the sums obviously stay squares (square times square is a square). So to tell whether solutions are truly distinct, you should make sure to divide out any such common multiples. That obviously wasn't done when writing this solution page.

axn 2019-02-03 14:47

[QUOTE=uau;507548]This lists the same 4+6 solution many times as a "different" one. If you multiply all the numbers by a second power, all the sums obviously stay squares (square times square is a square). So to tell whether solutions are truly distinct, you should make sure to divide out any such common multiples. That obviously wasn't done when writing this solution page.[/QUOTE]

Right. You should start out by normalizing such that smallest element is 0. Then divide out gcd (and list them in sorted order).

DukeBG 2019-02-04 11:50

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 [I]largest element of the set with the zero[/I]. (Assuming both sets contain non-negative numbers, of course).
I believe, though don't claim, that it is also the smallest possible [I]largest element of both sets[/I].

My [I]other[/I] 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.

uau 2019-02-04 15:09

[QUOTE=DukeBG;507621]My [I]other[/I] 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.[/QUOTE]
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.

SmartMersenne 2019-02-04 20:24

[QUOTE=DukeBG;507621]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 [I]largest element of the set with the zero[/I]. (Assuming both sets contain non-negative numbers, of course).
I believe, though don't claim, that it is also the smallest possible [I]largest element of both sets[/I].

My [I]other[/I] 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.[/QUOTE]

[0, 62640, 242352, 1112832] & [8649, 44944, 242064, 725904]

henryzz 2019-02-05 09:57

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.

DukeBG 2019-02-05 13:02

[QUOTE=SmartMersenne;507651][0, 62640, 242352, 1112832] & [8649, 44944, 242064, 725904][/QUOTE]
Thank you for shattering my [I]belief[/I]. My [I]claim[/I] 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=uau;507626]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.[/QUOTE]

Ahh... Ok, then.

SmartMersenne 2019-02-05 17:11

[QUOTE=DukeBG;507698]Thank you for shattering my [I]belief[/I]. My [I]claim[/I] 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]


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

uau 2019-02-05 18:27

[QUOTE=DukeBG;507698]Thank you for shattering my [I]belief[/I][/QUOTE] 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 2019-02-05 18:41

[QUOTE=henryzz;507693]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.[/QUOTE] 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 x[SUP]2[/SUP]+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, x[SUP]2[/SUP], and b+a2 = (b+a1) + (a2-a1) = x[SUP]2[/SUP]+D).


If x[SUP]2[/SUP]+D=y[SUP]2[/SUP], then D=y[SUP]2[/SUP]-x[SUP]2[/SUP]=(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.

DukeBG 2019-02-05 20:05

[QUOTE=uau;507722] 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.[/QUOTE]

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?[/QUOTE]
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.

henryzz 2019-02-06 10:48

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.

uau 2019-02-06 12:55

[QUOTE=henryzz;507804]Using my current method I think can do an exhaustive search upto 1e9 in around 24 hours.[/QUOTE]
Exhaustive search of what? You'll find all solutions that have what parameter under 1e9? All the numbers in both sets are below that?

henryzz 2019-02-06 14:26

[QUOTE=uau;507815]Exhaustive search of what? You'll find all solutions that have what parameter under 1e9? All the numbers in both sets are below that?[/QUOTE]

a1, a2 etc below 1e9. Thinking about it a5 and a6 can be any size in my code.

henryzz 2019-02-22 13:04

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

uau 2019-02-22 21:21

[QUOTE=henryzz;509126]Only just noticed that all the 4,6 solutions at the end are wrong. 1899+1899 is not square.[/QUOTE]
They're just written in a different format. The linked-to page has an explanation.

A=[2988, 5052, 12108, 34812]; B=[2988, 4356, 5787, 11164, 17046, 23948]
That's the same solution as what's written earlier as
A=[0, 16594560, 137675520, 1202947200]; B=[8928144, 18974736, 33489369, 124634896, 290566116, 573506704]

[QUOTE]@uau What were your search limits for this puzzle? Did you search for 5,5 solutions?[/QUOTE]I checked everything with a difference of squares below 4e9, and a somewhat pruned subset for differences below 8e9. Those had no solutions larger than 4+6.

henryzz 2019-03-05 12:15

I have changed my search strategy somewhat(not trying for an exhaustive search) and found a solution with 3 As(including 0) and 30 Bs.

One of the big things that helped was only looking at As divisible by primorials. I am finding more and more Bs as I increase the multiplier to larger primorials. I suspect that it might be possible to construct solutions of any size by increasing the primorial. I haven't written the code yet to check whether these would extend to nice solutions with 4 As. Current results look promising in that regard though.

Dr Sardonicus 2019-03-05 15:03

At one point, I had hopes of producing formulaic solutions. And, for the case of two sets of two numbers each, it's actually pretty easy. With the 2x2 matrix of squares [a^2, b^2; c^2, c^2] you have the relation

a^2 - b^2 = c^2 - d^2, or a^2 + d^2 = c^2 + b^2.

OK, just use the usual formula for a product of two sums of two squares.

Unfortunately, I was unable to expand on this idea. It is possible that quaternions etc might be used to satisfy some of the conditions that crop up in certain cases, but I didn't pursue this.

I looked at single-variable polynomials, and did not see any promising lines of attack.

The sort of simultaneous conditions that crop up are curious. The simultaneous equality of several differences of two squares points to numbers with lots of factors. For this reason, using primorials would seem to increase the odds of success...

henryzz 2019-03-05 15:50

I have discovered an overflow bug in my code. I think that the 3 and 30 solution might be optimistic.

Dr Sardonicus 2019-03-05 18:51

Curiously, I completely failed to notice a similar identity to the sum-of-two-squares identity, and one more directly applicable to the problem, for the product of two [i]differences[/i] of two squares, namely

(a^2 - b^2)*(c^2 - d^2) = (a*c +/- b*d)^2 - (a*d +/- b*c)^2.

As with the sum-of-two-squares identity, the product of k factors gives 2^(k-1) formally different expressions of the product as a difference of two squares. Alas, the expressions involve terms of total degree k. There is also a "head-to-tail" property of the various conditions that arise in the problem, which I didn't see how to use efficiently. Taking the example from the solutions

A=[9, 28224, 419904, 3968064]; B=[0, 47952, 259072, 2442960]

and letting M[sub]ij[/sub] = A[sub]i[/sub] + B[sub]j[/sub], we see that taking the difference of row j and row i of M gives the constant difference A[sub]j[/sub] - A[sub]i[/sub]. (Similarly with differences of two columns)

Taking row 2 - row 1, row 3 - row 2, and row 4 - row 3 we find the conditions

168^2 - 3^2 = 276^2 - 219^2 = 536^2 - 509^2 = 1572^2 - 1536^2,

648^2 - 168^2 = 684^2 - 276^2 = 824^2 - 536^2 = 1692^2 - 1572^2, and

1992^2 - 648^2 = 2004^2 - 684^2 = 2056^2 - 824^2 = 2532^2 - 1692^2

where the "head" of each expression in one set of conditions becomes the "tail" of an expression in the next.

henryzz 2019-03-05 19:54

I have fixed my bug and my best is now 3 and 16

uau 2019-03-06 20:56

[QUOTE=henryzz;510195]I have fixed my bug and my best is now 3 and 16[/QUOTE]
I ran my program for size 3 for a couple of hours, it found 3+18:
[31788, 237588, 971412]
[31788, 35210, 68936, 80460, 172060, 202104, 320040, 398216, 485352, 802935, 1069110, 1166760, 1223576, 1759940, 2145640, 3024801, 4809410, 32998140]

henryzz 2019-03-31 22:50

Realized it doesn't need to be primorials.

99% sure this is a correct 3+23:
A1: 0 A2: 2945209595328000 A3: 9277150506624000


Running out of space in a long which is a nuisance.

henryzz 2019-04-09 13:34

[QUOTE=henryzz;512334]Realized it doesn't need to be primorials.

99% sure this is a correct 3+23:
A1: 0 A2: 2945209595328000 A3: 9277150506624000


Running out of space in a long which is a nuisance.[/QUOTE]

Another improvement:

3+25: A1: 0 A2: 11009*M A3: 17081*M M: 21542104468684800000

My big issue currently is filtering the list of multipliers for M. Currently running 1 to 20000. Was filtering by the number of Bs the As can have but I am not too convinced by this as smaller multipliers are often better and that biases towards larger.


All times are UTC. The time now is 07:53.

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