October 2016

R. Gerbicz · 2016-10-02, 11:13

Ponder This, October 2016

a1call · 2016-10-02, 14:43

Quote:

Message to the solvers: Due to a technical limitation, solvers for October's challenge will only be published at the end of the month.

Yet there are already 60 names on the page on October 2nd.

fivemack · 2016-10-02, 17:24

What a particularly uninteresting problem - ten lines of Pari code to munge through it in a few hours (and it can be a few minutes if you're willing to accept prior knowledge of the answer). It makes you wonder whether the setter was unaware of how big the libraries have grown now and expected people to write the calculate-pi function too.

(I think you can get by with 1200 digit precision, which is really not that much, and it takes under 40 minutes)

Batalov · 2016-10-02, 17:58

Boy, I feel even a bit glad that I forgot to look up this one...

For the first time in a few years, I think I could get to "meta-solve" the category "solve 10 last problems" in Project Euler. I have one left, but it's tough! PE566...
________________________

EDIT: The answers for up to 8-digits strings are
L=2 38s with 35
L=3 301s with 459
L=4 818s with 1384
L=5 sikrit with XXXXX
L=6 18032s with 029095
L=7 34090s with 1718077
L=8 324724s with 39668259

R. Gerbicz · 2016-10-02, 18:22

Quote:

Originally Posted by fivemack

It makes you wonder whether the setter was unaware of how big the libraries have grown now

I don't think that. There are easier problems, this was one such a problem.

Batalov · 2016-10-03, 00:11

For L=9, the answer is 941873747 with a bit over 2mega-seconds (557:22:48)
For L=10, the answer is 2087746140 using 5645117s

LaurV · 2016-10-03, 09:50

I agree with Tom and Serge, this problem is totally uninteresting. Even without arbitrary precision math, one could get the "strings" from anywhere on the web (wolfram, etc) and do simple string processing.

R. Gerbicz · 2016-10-03, 09:53

For L=11: 17511073s with 38898554239, computed this in 16min using only PARI-Gp.

Batalov · 2016-10-03, 14:56

When I was 15, I wrote programs that computed pi, e, and M to a 100,000 digits (iirc), and my father ran them at the RFNC "super-computer" (which was BESM-6 and Elbrus), so this problem did get me to feel nostalgic for a split minute. The programs computed constants from scratch using school division and multiplication and were in Fortran and Algol-68 if memory serves.

R. Gerbicz · 2016-10-03, 17:42

If you like to compute these constants then see (for example): http://www.spoj.com/problems/PIVAL/ . On spoj you can find the other two constants challenge problem. Note that these has strict code size limit=4096 bytes. And you can find also a challenge for golden ratio, but with different scoring system.

Returning to the original problem:
For L=12: 173108889 sec;string=027143247568
For L=13: 396336569 sec;string=6766970531749
This time not used Pari-Gp.
For L=14 I've run out of memory.

Xyzzy · 2016-11-01, 13:35

https://www.research.ibm.com/haifa/p...tober2016.html

2016-10-02, 11:13	#1
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3²·179 Posts	October 2016 Ponder This, October 2016

2016-10-02, 17:58	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23505₈ Posts	Boy, I feel even a bit glad that I forgot to look up this one... For the first time in a few years, I think I could get to "meta-solve" the category "solve 10 last problems" in Project Euler. I have one left, but it's tough! PE566... ________________________ EDIT: The answers for up to 8-digits strings are L=2 38s with 35 L=3 301s with 459 L=4 818s with 1384 L=5 sikrit with XXXXX L=6 18032s with 029095 L=7 34090s with 1718077 L=8 324724s with 39668259 Last fiddled with by Batalov on 2016-10-02 at 23:58

2016-10-03, 00:11	#6
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3²·1,117 Posts	For L=9, the answer is 941873747 with a bit over 2mega-seconds (557:22:48) For L=10, the answer is 2087746140 using 5645117s Last fiddled with by Batalov on 2016-10-03 at 01:17 Reason: ...yes ...L=10.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
October 2017	Xyzzy	Puzzles	9	2017-11-07 15:18
October 2015	LaurV	Puzzles	3	2015-11-02 15:22
October 2014	Xyzzy	Puzzles	8	2014-11-02 19:03
13 October is approaching!	Joe O	Prime Sierpinski Project	1	2010-10-09 06:12
4.0 to 4.5 quake expected in San Francisco area October 20-24 2006.	lukethomas	Science & Technology	18	2006-11-13 03:51

2016-10-02, 17:24	#3
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	What a particularly uninteresting problem - ten lines of Pari code to munge through it in a few hours (and it can be a few minutes if you're willing to accept prior knowledge of the answer). It makes you wonder whether the setter was unaware of how big the libraries have grown now and expected people to write the calculate-pi function too. (I think you can get by with 1200 digit precision, which is really not that much, and it takes under 40 minutes)

2016-10-03, 09:50	#7
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 10100000100100₂ Posts	I agree with Tom and Serge, this problem is totally uninteresting. Even without arbitrary precision math, one could get the "strings" from anywhere on the web (wolfram, etc) and do simple string processing.

2016-10-03, 09:53	#8
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 64B₁₆ Posts	For L=11: 17511073s with 38898554239, computed this in 16min using only PARI-Gp.

2016-10-03, 14:56	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3²×1,117 Posts	When I was 15, I wrote programs that computed pi, e, and M to a 100,000 digits (iirc), and my father ran them at the RFNC "super-computer" (which was BESM-6 and Elbrus), so this problem did get me to feel nostalgic for a split minute. The programs computed constants from scratch using school division and multiplication and were in Fortran and Algol-68 if memory serves.

2016-10-03, 17:42	#10
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3²×179 Posts	If you like to compute these constants then see (for example): http://www.spoj.com/problems/PIVAL/ . On spoj you can find the other two constants challenge problem. Note that these has strict code size limit=4096 bytes. And you can find also a challenge for golden ratio, but with different scoring system. Returning to the original problem: For L=12: 173108889 sec;string=027143247568 For L=13: 396336569 sec;string=6766970531749 This time not used Pari-Gp. For L=14 I've run out of memory.

2016-11-01, 13:35	#11
Xyzzy Aug 2002 2×7×13×47 Posts	https://www.research.ibm.com/haifa/p...tober2016.html