mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-03-02, 15:48   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2·5·11·71 Posts
Default March 2016

https://www.research.ibm.com/haifa/p...March2016.html
Xyzzy is offline   Reply With Quote
Old 2016-03-02, 18:09   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
I haven't narrowed it enough to do anything useful with the question.
science_man_88 is offline   Reply With Quote
Old 2016-03-02, 18:16   #3
axn
 
axn's Avatar
 
Jun 2003

12AD16 Posts
Default

Using brute force exhaustive search (O(10^8)), I was able to find two solutions for n=15.
Here are the smaller solutions:
Code:
n=5 65766
n=5 69714
n=7 6317056
n=9 169605719
n=11 96528287587
There were none for n=13. I haven't looked for patterns with even number of digits.
axn is online now   Reply With Quote
Old 2016-03-02, 18:26   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by axn View Post
Using brute force exhaustive search (O(10^8)), I was able to find two solutions for n=15.
Here are the smaller solutions:
Code:
n=5 65766
n=5 69714
n=7 6317056
n=9 169605719
n=11 96528287587
There were none for n=13. I haven't looked for patterns with even number of digits.
the patterns I see that should hold regardless of length are related to the first n must be the end of a square reversed and the rest must match up to give those digits ( so the last has to be a number mod 10 that allows a square to end in the first digit hence the 1 and 0 combination (9^2)%10==1)
science_man_88 is offline   Reply With Quote
Old 2016-03-06, 16:21   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·709 Posts
Default

From Ibm Ponder This:

Update (07/03):
A solution with more than 20 digits will earn you a '**'.
R. Gerbicz is offline   Reply With Quote
Old 2016-03-07, 10:31   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

Quote:
Originally Posted by axn View Post
Using brute force exhaustive search (O(10^8)), I was able to find two solutions for n=15.
Here are the smaller solutions:
Code:
n=5 65766
n=5 69714
n=7 6317056
n=9 169605719
n=11 96528287587
There were none for n=13. I haven't looked for patterns with even number of digits.
n=8 90899553
LaurV is offline   Reply With Quote
Old 2016-03-12, 12:14   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

34·71 Posts
Default

Found the two n=15s

n=1 1
n=1 5
n=1 6
n=3 963
n=4 9,867
n=5 65,766
n=5 69,714
n=7 6,317,056
n=8 90,899,553
n=9 169,605,719
n=10 4,270,981,082
n=11 96,528,287,587
n=12 465,454,256,742
n=12 692,153,612,536

They seem to be getting rarer. Has anyone a clue of how many we should expect to find of a certain size?
Running a search upto 18 digits. This should take a while. 20 digits is out of my reach so far.
henryzz is online now   Reply With Quote
Old 2016-03-13, 10:25   #8
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

3×7×53 Posts
Default

Is there an elegant way to solve this problem or is writing a program and cycling through candidates the only way to go?

Sometimes it is difficult to tell when brute-force is actually the intended solution method. I started playing around with a few examples (and even built a grammar-school 15-digit by 15-digit multiplication problem to build up the product line-by-line in Excel) but things get unwieldy fairly quickly. As in GIMPS, knowing the position and size of potential carries becomes vital...but there is no easy way to really do this here.
NBtarheel_33 is offline   Reply With Quote
Old 2016-03-13, 14:31   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

131678 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
Is there an elegant way to solve this problem or is writing a program and cycling through candidates the only way to go?

Sometimes it is difficult to tell when brute-force is actually the intended solution method. I started playing around with a few examples (and even built a grammar-school 15-digit by 15-digit multiplication problem to build up the product line-by-line in Excel) but things get unwieldy fairly quickly. As in GIMPS, knowing the position and size of potential carries becomes vital...but there is no easy way to really do this here.
Quadratic residues reduce the candidate pool massively. I will explain my method in full once the deadline is up. Found an 18 digit one last night.
I think I may have hit on the way to get to 20 digits today. The squaring was the slowest bit for me. I should be able to go from one square to another though. n^2-(n-x)^2=2*x*n-x^2 which is much easier to calculate and add than do another square.

Last fiddled with by henryzz on 2016-03-13 at 14:31
henryzz is online now   Reply With Quote
Old 2016-03-13, 14:53   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

893210 Posts
Default

Some supermod should put your post in SPOILER ALERT.
You actually disclosed the method...
LaurV is offline   Reply With Quote
Old 2016-03-16, 01:57   #11
ramshanker
 
ramshanker's Avatar
 
"Ram Shanker"
May 2015
Delhi

2516 Posts
Default

Are there no 14 & 18 digit answer to this? My program didn't turn-up anything. I am having doubt whether I am doing it right or not.

Though it did reproduce the 10 & 12 digit ones posted above. My code is for even digits only.

Last fiddled with by ramshanker on 2016-03-16 at 01:58
ramshanker is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
March 2018 Xyzzy Puzzles 2 2018-04-08 13:45
March 2017 R. Gerbicz Puzzles 1 2017-04-03 10:57
March 2015 Xyzzy Puzzles 15 2015-04-02 02:19
March Madness 2006 Prime95 Lounge 20 2006-03-21 04:35
gmp 4.2 due in March Mystwalker GMP-ECM 4 2006-02-01 12:00

All times are UTC. The time now is 16:42.

Sun Nov 29 16:42:42 UTC 2020 up 80 days, 13:53, 4 users, load averages: 1.06, 1.08, 1.08

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.