Ponder This Challenge - May 2013 - Computing a polynomial

Ponder This Challenge:

Define a program to be a list of commands, each command of the form Variable_1 <=- Variable_2 Operation constant or Variable_1 <=- Variable_2 Operation Variable_3 where operation can be either addition, multiplication or modulo.

Here is an example of a program which computes the function f(x) = 1+x+x^2+x^4 (modulo 2233393)

a=x*47518 b=a*a c=x+1 d=c+b e=b*b f=e+d g=f mod 2233393

Find another program which computes the same function which uses a multiplying two variables at most twice and its last two commands are: a multiplication of two variables and a modulo computation.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  The intended solution was to factor 1+x+x^2+x^4 to (x^2+ax+b)(x^2+cx+d) modulo 2233393. Note that 2233393 = 19*41*47*61, so we can factor modulo each one of the four primes and combine the resulting coefficients using the Chinese remainder theorem. A possible answer is y=x*x a=638773*x a=y+a a=1613501+a b=1594620*x b=y+b b=b+1831287 z=a*b z=z mod 2233393

  As for the bonus question - it's the June 2012 question from the UYHIP web site. Visit the site on July to learn about their solution.

Solvers

• *Jan Fricke (04/30/2013 02:36 PM EDT)
• Thomas Mack (05/01/2013 12:43 AM EDT)
• János Kramár (05/01/2013 01:54 AM EDT)
• Siji Feng (05/01/2013 02:02 AM EDT)
• Robin Ryder (05/01/2013 02:15 AM EDT)
• *Radu-Alexandru Todor (05/01/2013 05:07 AM EDT)
• *Florian Fischer (05/01/2013 05:38 AM EDT)
• Frederik Kaster (05/01/2013 06:51 AM EDT)
• Adrian Orzepowski (05/01/2013 07:22 AM EDT)
• Pete Gerritson (05/01/2013 10:39 AM EDT)
• Alan Murray (05/01/2013 11:14 AM EDT)
• Pavan Vaswani (05/01/2013 01:41 PM EDT)
• Paul Safier (05/02/2013 02:35 AM EDT)
• Arthur Vause (05/02/2013 08:20 AM EDT)
• Peter Holdsworth (05/02/2013 12:05 PM EDT)
• Don Dodson & Dave Dodson (05/03/2013 12:28 AM EDT)
• Siva Dirisala (05/03/2013 03:44 AM EDT)
• J (05/03/2013 07:38 AM EDT)
• oseph DeVincentis (05/03/2013 07:38 AM EDT)
• Andrew Gacek (05/03/2013 09:03 AM EDT)
• Olivier Mercier (05/03/2013 09:18 AM EDT)
• Alex Fleischer (05/03/2013 10:57 AM EDT)
• John Tromp (05/03/2013 12:52 PM EDT)
• *Eric Harley (05/03/2013 02:00 PM EDT)
• David Greer (05/03/2013 09:40 PM EDT)
• Yasodhar Patnaik (05/03/2013 11:28 PM EDT)
• Albert Stadler (05/04/2013 12:16 PM EDT)
• *Alex Wagner (05/04/2013 02:42 PM EDT)
• Xianchao Xie (05/04/2013 07:29 PM EDT)
• Gerhard + Klaus Hoffmann (05/04/2013 02:49 PM EDT)
• Liubing Yu (05/05/2013 01:23 PM EDT)
• Antonio García Astudillo (05/05/2013 04:05 PM EDT)
• Joe Klobusicky (05/05/2013 04:59 PM EDT)
• Amos Guler (05/06/2013 09:45 AM EDT)
• Peijie You (05/07/2013 01:15 AM EDT)
• Pushkar S Joglekar (05/07/2013 04:58 AM EDT)
• Harald Bögeholz (05/07/2013 02:07 PM EDT)
• Clive Tong (05/07/2013 02:43 PM EDT)
• Dan Dima (05/07/2013 03:57 PM EDT)
• Javier Rodriguez (05/07/2013 05:09 PM EDT)
• *Armin Krauss (05/08/2013 01:03 PM EDT)
• Todd Will (05/08/2013 03:09 PM EDT)
• Rodrigo Exterckötter Tjäder (05/08/2013 08:14 PM EDT)
• Swaraj Dash (05/07/2013 09:49 AM EDT)
• Adir HaCohen (05/09/2013 07:00 PM EDT)
• *Lorenzo Gianferrari Pini (05/10/2013 07:14 AM EDT)
• Mark Pervovskiy (05/10/2013 09:44 AM EDT)
• *Álvaro Begué (05/10/2013 09:54 AM EDT)
• *I. J. Kennedy (05/10/2013 12:01 PM EDT)
• Daniel Branscombe (05/10/2013 08:31 PM EDT)
• Rogerio Ponce (05/11/2013 04:33 AM EDT)
• Seung Min Park (05/12/2013 09:47 AM EDT)
• *Antoine Comeau (05/12/2013 04:01 PM EDT)
• Andreas Stiller (05/13/2013 06:24 AM EDT)
• *Serge Gautier (05/13/2013 04:04 PM EDT)
• *Motty Porat (05/15/2013 03:53 PM EDT)
• *Tom Harley (05/15/2013 04:23 PM EDT)
• Zilin Jiang (05/15/2013 10:57 PM EDT)
• Andreas Razen (05/19/2013 03:46 AM EDT)
• Jason Lee & Jacob Woolcutt (05/19/2013 09:36 AM EDT)
• Franza Cavalcante Jr (05/22/2013 11:09 AM EDT)
• Rongheng Lin (05/23/2013 01:38 PM EDT)
• Nyles Heise (05/23/2013 11:01 PM EDT)
• William Kang (05/25/2013 08:33 AM EDT)
• Ian Wright (05/25/2013 09:15 AM EDT)
• Daniel Biti (05/26/2013 10:00 AM EDT)
• n (05/26/2013 10:00 AM EDT)
• Ehud Schreiber (05/27/2013 01:44 AM EDT)
• Michael Lim (05/29/2013 08:21 PM EDT)
• Sergey Grishaev (06/01/2013 06:05 AM EDT)