mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2014-10-26, 23:58   #1
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

22·7·47 Posts
Default Project Euler 486

So I've been doing these problems again lately and figured I'd take a look at the newest, number 486.

However, I think I must be missing something about the setup of it:

---------------
Let F5(n) be the number of strings s such that:

s consists only '0's and '1's,
s has length at most n, and
s contains a palindromic substring of length at least 5.

For example, F5(4) = 0, F5(5) = 8, F5(6) = 42 and F5(11) = 3844.
---------------

Clearly F(4) = 0, because there are no substrings with length 5.

I'm also fairly happy with F(5) = 8.

My issue is with F(6) = 42. I can't figure how this is the case. For strings of length exactly 6, I count 28 with a required palindromic substring. Since the problem states that F(n) is defined as strings AT MOST length n, then we can include all of the length 5 strings too. So this would bring the answer for F(6) to 36.

Even if it were as simple as adding 1 extra bit to either the beginning or end of a palindromic string of 5, there would only be 4*8 = 32 solutions of length 6 (of course, some are double-ups that must be accounted for). But even in this case, F(6) = 40, still shy of 42.

I know that this is a new problem, so it could be a mistake. However 44 people have solved this one, so I'm unsure.
lavalamp is offline   Reply With Quote
Old 2014-10-27, 00:53   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217368 Posts
Default

Quote:
Originally Posted by lavalamp View Post
...s contains a palindromic substring of length at least 5. <-- (not just 5)
...
I had no problem with the formulation.
I reproduced D(5*10^9), too. I still have problem with final scale-up. I have an idea how to do it.
Batalov is offline   Reply With Quote
Old 2014-10-27, 02:57   #3
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

22×7×47 Posts
Default

Ohhhhhhhhhhhh, I see. That makes it so much harder too.
lavalamp is offline   Reply With Quote
Old 2015-02-01, 07:36   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Unhappy PE 501

It is always interesting when one's answer to a problem is wrong not because the solution is wrong, but because of a bug in Pari.

A certain (rather straightforward) solution for PE 501 gives the wrong answer with Pari 2.7.1, but after an off-chance-grabbing-at-straws upgrade to 2.7.2 ...the answer becomes right! Ugh. Something was amiss with prime()/primepi(), and now apparently fixed.
Batalov is offline   Reply With Quote
Old 2015-02-01, 20:06   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001100112 Posts
Default

Quote:
Originally Posted by Batalov View Post
It is always interesting when one's answer to a problem is wrong not because the solution is wrong, but because of a bug in Pari.

A certain (rather straightforward) solution for PE 501 gives the wrong answer with Pari 2.7.1, but after an off-chance-grabbing-at-straws upgrade to 2.7.2 ...the answer becomes right! Ugh. Something was amiss with prime()/primepi(), and now apparently fixed.
Can you give more information? I'd like to reproduce this.
CRGreathouse is offline   Reply With Quote
Old 2015-02-01, 20:14   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23DE16 Posts
Default

I will PM you. I don't want to "post the solution". (And I have no doubt that you can solve it anyway, and even more elegantly!)

Maybe I'll be able to make the debug case smaller. Anyway - the bug was in 2.7.1, seems to be fixed in 2.7.2. Not the other way around.

EDIT: I removed the code that gives away half of the PE 501 solution, because see below...

Last fiddled with by Batalov on 2015-02-07 at 18:09
Batalov is offline   Reply With Quote
Old 2015-02-04, 03:37   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts
Default

I simplified the bug now to a single call (found in 2.6.0 -- 2.7.1, both linux and windows):
Code:
# ./gp -p500000000

? primepi(450450450)
%1 = 23875519  (in 2.7.2, or <=2.5.5)
%1 = 23875520  (in 2.7.1, 2.7.0, 2.6.x with precomputed primes)

# but if you don't precompute primes, the answer is correct, in both cases! 
# the calculation of my script without precomputed primes is too slow, so they have to be precomputed
Batalov is offline   Reply With Quote
Old 2015-02-04, 14:01   #8
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

3×179 Posts
Default

Quote:
Originally Posted by Batalov View Post
I simplified the bug now to a single call (found in 2.6.0 -- 2.7.1, both linux and windows):
Code:
# ./gp -p500000000

? primepi(450450450)
%1 = 23875519  (in 2.7.2, or <=2.5.5)
%1 = 23875520  (in 2.7.1, 2.7.0, 2.6.x with precomputed primes)

# but if you don't precompute primes, the answer is correct, in both cases! 
# the calculation of my script without precomputed primes is too slow, so they have to be precomputed
Perhaps this?
Code:
commit 758f760868e38edb7b4e88f3e1759282623366e6
Author: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
Date:   Sat Mar 8 08:41:14 2014 +0100

    29- primepi(N >= 2^32 or 2^64) off by 1
    
    + remove useless HACK
Code:
index f622ba2..931abf7 100644
--- a/src/basemath/prime.c
+++ b/src/basemath/prime.c
@@ -1031,22 +1031,24 @@ uprimepi(ulong a)
   {
     byteptr d;
     prime_table_next_p(a, &d, &p, &n);
+    return p == a? n: n-1;
   }
   else
   {
     long i = prime_table_closest_p(a);
     forprime_t S;
     p = prime_table[i].p;
-    if (p > maxp)
+    if (p > a)
     {
       i--;
       p = prime_table[i].p;
     }
+    /* p = largest prime in table <= a */
     n = prime_table[i].n;
     (void)u_forprime_init(&S, p+1, a);
     for (; p; n++) p = u_forprime_next(&S);
+    return n-1;
   }
-  return p == a? n: n-1;
 }
 
 GEN
@@ -1061,7 +1063,6 @@ primepi(GEN x)
   if (signe(N) <= 0) return gen_0;
   avma = av; l = lgefint(N);
   if (l == 3) return utoi(uprimepi(N[2]));
-  new_chunk(l); /*HACK*/
   i = prime_table_len-1;
   p = prime_table[i].p;
   n = prime_table[i].n;
@@ -1069,7 +1070,7 @@ primepi(GEN x)
   nn = setloop(utoipos(n));
   pp = gen_0;
   for (; pp; incloop(nn)) pp = forprime_next(&S);
-  avma = av; return icopy(nn);
+  return gerepileuptoint(av, subiu(nn,1));
 }
 
 /* pi(x) < x/log x * (1 + 1/log x + 2.51/log^2 x)), x>=355991 [ Dusart ]
Edit: That doesn't seem to be it since 2.7.0 was released after that change.

Last fiddled with by ldesnogu on 2015-02-04 at 14:24
ldesnogu is offline   Reply With Quote
Old 2015-02-04, 14:28   #9
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

3×179 Posts
Default

Next try

Code:
[ldesnogu@localhost pari]$ git show c2c67fa04290844d8dbd719cdf1d473c4463636c
commit c2c67fa04290844d8dbd719cdf1d473c4463636c
Author: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
Date:   Mon May 26 11:56:00 2014 +0200

    25- (gp -p N) or (primelimit=N in gprc_ for N >= 436273290 resulted in an
       incorrect primetable. N.B. Such commands are now useless: needed primes
       are produced dynamically anyway.

diff --git a/CHANGES b/CHANGES
index 551036b..d13ec2f 100644
--- a/CHANGES
+++ b/CHANGES
@@ -7,6 +7,9 @@ Done for version 2.7.2 (released ??/??/2014):
   Fixed
     1- gaffsg(0, t_PADIC): wrong valuation                                [F21]
     2- (t_INTMOD with word-sized modulus)^(huge negative power) [#1584]   [F24]
+    3- (gp -p N) or (primelimit=N in gprc_ for N >= 436273290 resulted in an
+       incorrect primetable. N.B. Such commands are now useless: needed primes
+       are produced dynamically anyway.                                   [F25]
 
 Done for version 2.7.1 (released 16/05/2014):
 [last column crossreferences current development release 2.8.0]
diff --git a/src/basemath/arith2.c b/src/basemath/arith2.c
index bc650ff..5a671c7 100644
--- a/src/basemath/arith2.c
+++ b/src/basemath/arith2.c
@@ -358,7 +358,7 @@ sieve_chunk(byteptr known_primes, ulong s, byteptr data, ulo
   }
 }
 
-/* assume maxnum <= 436273290 < 2^29 */
+/* assume maxnum <= 436273289 < 2^29 */
 static void
 initprimes0(ulong maxnum, long *lenp, ulong *lastp, byteptr p1)
 {
@@ -435,16 +435,18 @@ maxprime(void) { return diffptr ? _maxprime : 0; }
 void
 maxprime_check(ulong c) { if (_maxprime < c) pari_err_MAXPRIME(c); }
 
-/* We ensure 65302 <= maxnum <= 436273290: the LHS ensures modular function
- * have enough fast primes to work, the RHS ensures that p_{n+1} - p_n < 255 */
+/* We ensure 65302 <= maxnum <= 436273289: the LHS ensures modular function
+ * have enough fast primes to work, the RHS ensures that p_{n+1} - p_n < 255
+ * (N.B. RHS would be incorrect since initprimes0 would make it odd, thereby
+ * increasing it by 1) */
 byteptr
 initprimes(ulong maxnum, long *lenp, ulong *lastp)
 {
   byteptr t;
   if (maxnum < 65537)
     maxnum = 65537;
-  else if (maxnum > 436273290)
-    maxnum = 436273290;
+  else if (maxnum > 436273289)
+    maxnum = 436273289;
   t = (byteptr)pari_malloc((size_t) (1.09 * maxnum/log((double)maxnum)) + 146);
   initprimes0(maxnum, lenp, lastp, t);
   return (byteptr)pari_realloc(t, *lenp);
ldesnogu is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Project Euler jhs Puzzles 29 2016-09-04 17:05
Project Euler #372 lavalamp Puzzles 165 2012-05-24 16:40
Euler (6,2,5) details. Death Math 10 2011-08-03 13:49
Project Euler Mini-Geek Lounge 2 2009-10-23 17:19
Bernoulli and Euler numbers (Sam Wagstaff project) fivemack Factoring 4 2008-02-24 00:39

All times are UTC. The time now is 15:47.

Tue Dec 1 15:47:25 UTC 2020 up 82 days, 12:58, 3 users, load averages: 2.71, 2.22, 1.98

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.