Category Archives: Mathematical Puzzles

Clock times using 6 numbers

A number puzzle has recently been given by Column8 in the Sydney Morning Herald newspaper.

The proposer wondered what “clock-times” between 1:00 am and 8:00 am he could make with the six numbers 75, 25, 1, 3, 5 and 7 (reminiscent of the puzzles on the TV game show Letters and Numbers).

For example, 7:40 can obviously be calculated as (75 – 1) • (3 + 7) i.e. 74 • 10 giving 740 (7:40 on the clock, so to speak). This also means that numbers like 570 or 799 do not count since they are not clock times.

It was actually claimed that every time except one had at least one solution. What a laborious thing to verify, without a decent little computer program of course.

However, starting from the top and working backwards, I soon found several gaps:

8:00 (75 + 25) • (1 + 7)

7:59

7:58 (75 – 25) • 3 • 5 + 7 + 1 OR (75 – 25 + 1) • 3 • 5 – 7

7:57 (75 + 25 + 3 + 5) • 7 + 1

7:56 75 • (3 + 7) + 5 + 1

7:55 75 • (3 + 7) + 5

7:54 75 • (3 + 7) + 5 – 1

7:53 ((75 – 25) • 5 + 1) • 3

7:52

7:51: 75 • (3 + 7) + 1

7:50 75 • (3 + 7)

7:49 75 • (3 + 7) – 1

7:48

7:47

7:46 75 • (3 + 7) – 5 + 1

7:45 75 • (3 + 7) – 5

7:44 75 • (3 + 7) – 5 – 1

7:43 (75 – 25) • 3 • 5 – 7

7:42 (75 + 25 + 1 + 5) • 7

7:41

7:40 (75 – 1) • (3 + 7)

The proposer has now revealed that all of the numbers except 7:59 have solutions. I was amazed.

After more scribbling, here’s my solution from “outside the square” for this number:

7:59 (75 + 1) • (3 + 7) – ( √ 25 ) / 5 = 76 • 10 – 1

Who can deny that square root is an arithmetic operation?

There remain the other incomplete entries – any solutions?

A lucky factorization

Factorizations, using the post-processing program Msieve, usually take an average of 2 attempted sqrt calculations to split composite numbers into two factors. Sometimes we are unlucky and it takes three, four or more times. If there are more factors, more sqrts are required.

In this case it took 33. Yes, that’s right 33. The mathematical probability is 1/2 for each step to split the number into two factors. Here, things went wrong when almost every step said “Newton iteration failed to converge”, so it seems there are hidden bugs there somewhere.

The sqrt phase started on Saturday morning (Oct 29, 2011) and continued until Monday morning (Oct 31).

The Lanczos matrix step said that it had found 40 nontrivial dependencies, so if all 40 had failed, we would normally either reduce the number of relations from the 73,520,074 found or continue the sieving to find more. Either way would involve another possible 21+ hours of matrix inversion followed by the sqrt steps.

What a relief.

By the way, the number being factored was the 220-digit composite from 13148 + 48131 = 7 • C220.

Results were posted as message 2433 on XYYXF (in Yahoo Groups) Mon, 31 Oct 2011:

(See http://tech.groups.yahoo.com/group/xyyxf/message/2433 )

Factor Results for C220_131_48: (by SNFS) — Dep 33 with many errors

prp46 factor:
1359529908141779271184277189171489400662\
097997

prp62 factor:
1911874395935236064025593241578389628028\
2870589357747809888407

prp113 factor:
9608507490790427829994761954763147371788\
3403021818589315152706842120055325258281\
894963227008240264378713088470181

–Bob.

This number came out at Dependency 33 after many mysterious “failed to converge” errors:


Fri Oct 28 13:19:41 2011 commencing linear algebra
Fri Oct 28 13:19:43 2011 read 3845291 cycles
Fri Oct 28 13:19:48 2011 cycles contain 10133440 unique relations
Fri Oct 28 13:21:11 2011 read 10133440 relations
Fri Oct 28 13:21:25 2011 using 20 quadratic characters above 536870684
Fri Oct 28 13:22:11 2011 building initial matrix
Fri Oct 28 13:24:02 2011 memory use: 1329.5 MB
Fri Oct 28 13:24:03 2011 read 3845291 cycles
Fri Oct 28 13:24:05 2011 matrix is 3845114 x 3845291 (1134.9 MB) with weight 334702241 (87.04/col)
Fri Oct 28 13:24:05 2011 sparse part has weight 259050938 (67.37/col)
Fri Oct 28 13:24:41 2011 filtering completed in 2 passes
Fri Oct 28 13:24:41 2011 matrix is 3844718 x 3844895 (1134.9 MB) with weight 334691813 (87.05/col)
Fri Oct 28 13:24:41 2011 sparse part has weight 259047871 (67.37/col)
Fri Oct 28 13:24:56 2011 read 3844895 cycles
Fri Oct 28 13:24:57 2011 matrix is 3844718 x 3844895 (1134.9 MB) with weight 334691813 (87.05/col)
Fri Oct 28 13:24:57 2011 sparse part has weight 259047871 (67.37/col)
Fri Oct 28 13:24:57 2011 saving the first 48 matrix rows for later
Fri Oct 28 13:24:59 2011 matrix is 3844670 x 3844895 (1092.3 MB) with weight 265839582 (69.14/col)
Fri Oct 28 13:24:59 2011 sparse part has weight 247878277 (64.47/col)
Fri Oct 28 13:24:59 2011 matrix includes 64 packed rows
Fri Oct 28 13:24:59 2011 using block size 65536 for processor cache size 8192 kB
Fri Oct 28 13:25:12 2011 commencing Lanczos iteration (8 threads)
Fri Oct 28 13:25:12 2011 memory use: 1301.2 MB
Fri Oct 28 13:25:28 2011 linear algebra at 0.0%, ETA 21h11m
Sat Oct 29 10:02:43 2011 lanczos halted after 60804 iterations (dim = 3844670)
Sat Oct 29 10:02:51 2011 recovered 40 nontrivial dependencies
Sat Oct 29 10:02:51 2011 BLanczosTime: 74590
Sat Oct 29 10:02:51 2011
Sat Oct 29 10:02:51 2011 commencing square root phase
Sat Oct 29 10:02:51 2011 reading relations for dependency 1
Sat Oct 29 10:02:52 2011 read 1922895 cycles
Sat Oct 29 10:02:54 2011 cycles contain 5065912 unique relations
Sat Oct 29 10:03:58 2011 read 5065912 relations
Sat Oct 29 10:04:24 2011 multiplying 5065912 relations
Sat Oct 29 10:17:44 2011 multiply complete, coefficients have about 133.03 million bits
Sat Oct 29 10:17:45 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 10:17:45 2011 initial square root is modulo 53
Sat Oct 29 10:53:50 2011 Newton iteration failed to converge
Sat Oct 29 10:53:50 2011 algebraic square root failed
Sat Oct 29 10:53:50 2011 reading relations for dependency 2
Sat Oct 29 10:53:51 2011 read 1921916 cycles
Sat Oct 29 10:53:54 2011 cycles contain 5066996 unique relations
Sat Oct 29 10:54:57 2011 read 5066996 relations
Sat Oct 29 10:55:23 2011 multiplying 5066996 relations
Sat Oct 29 11:13:17 2011 multiply complete, coefficients have about 133.06 million bits
Sat Oct 29 11:13:17 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 11:13:18 2011 initial square root is modulo 53
Sat Oct 29 12:09:36 2011 Newton iteration failed to converge
Sat Oct 29 12:09:36 2011 algebraic square root failed
Sat Oct 29 12:09:36 2011 reading relations for dependency 3
Sat Oct 29 12:09:36 2011 read 1922386 cycles
Sat Oct 29 12:09:40 2011 cycles contain 5067592 unique relations
Sat Oct 29 12:10:55 2011 read 5067592 relations
Sat Oct 29 12:11:34 2011 multiplying 5067592 relations
Sat Oct 29 12:32:27 2011 multiply complete, coefficients have about 133.08 million bits
Sat Oct 29 12:32:28 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 12:32:28 2011 initial square root is modulo 53
Sat Oct 29 13:28:48 2011 Newton iteration failed to converge
Sat Oct 29 13:28:48 2011 algebraic square root failed
Sat Oct 29 13:28:48 2011 reading relations for dependency 4
Sat Oct 29 13:28:49 2011 read 1920514 cycles
Sat Oct 29 13:28:53 2011 cycles contain 5062796 unique relations
Sat Oct 29 13:30:07 2011 read 5062796 relations
Sat Oct 29 13:30:46 2011 multiplying 5062796 relations
Sat Oct 29 13:51:37 2011 multiply complete, coefficients have about 132.95 million bits
Sat Oct 29 13:51:38 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 13:51:38 2011 initial square root is modulo 53
Sat Oct 29 14:47:58 2011 Newton iteration failed to converge
Sat Oct 29 14:47:58 2011 algebraic square root failed
Sat Oct 29 14:47:58 2011 reading relations for dependency 5
Sat Oct 29 14:47:59 2011 read 1921542 cycles
Sat Oct 29 14:48:03 2011 cycles contain 5063820 unique relations
Sat Oct 29 14:49:18 2011 read 5063820 relations
Sat Oct 29 14:49:57 2011 multiplying 5063820 relations
Sat Oct 29 15:10:49 2011 multiply complete, coefficients have about 132.98 million bits
Sat Oct 29 15:10:50 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 15:10:50 2011 initial square root is modulo 53
Sat Oct 29 16:07:08 2011 reading relations for dependency 6
Sat Oct 29 16:07:09 2011 read 1921070 cycles
Sat Oct 29 16:07:13 2011 cycles contain 5062324 unique relations
Sat Oct 29 16:08:27 2011 read 5062324 relations
Sat Oct 29 16:09:06 2011 multiplying 5062324 relations
Sat Oct 29 16:29:56 2011 multiply complete, coefficients have about 132.94 million bits
Sat Oct 29 16:29:57 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 16:29:57 2011 initial square root is modulo 53
Sat Oct 29 17:26:15 2011 reading relations for dependency 7
Sat Oct 29 17:26:16 2011 read 1922582 cycles
Sat Oct 29 17:26:20 2011 cycles contain 5066668 unique relations
Sat Oct 29 17:27:35 2011 read 5066668 relations
Sat Oct 29 17:28:14 2011 multiplying 5066668 relations
Sat Oct 29 17:49:07 2011 multiply complete, coefficients have about 133.05 million bits
Sat Oct 29 17:49:07 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 17:49:08 2011 initial square root is modulo 53
Sat Oct 29 18:45:29 2011 Newton iteration failed to converge
Sat Oct 29 18:45:29 2011 algebraic square root failed
Sat Oct 29 18:45:29 2011 reading relations for dependency 8
Sat Oct 29 18:45:29 2011 read 1921431 cycles
Sat Oct 29 18:45:33 2011 cycles contain 5063694 unique relations
Sat Oct 29 18:46:48 2011 read 5063694 relations
Sat Oct 29 18:47:28 2011 multiplying 5063694 relations
Sat Oct 29 19:08:20 2011 multiply complete, coefficients have about 132.97 million bits
Sat Oct 29 19:08:21 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 19:08:21 2011 initial square root is modulo 53
Sat Oct 29 20:04:44 2011 Newton iteration failed to converge
Sat Oct 29 20:04:44 2011 algebraic square root failed
Sat Oct 29 20:04:44 2011 reading relations for dependency 9
Sat Oct 29 20:04:45 2011 read 1922781 cycles
Sat Oct 29 20:04:49 2011 cycles contain 5069110 unique relations
Sat Oct 29 20:06:04 2011 read 5069110 relations
Sat Oct 29 20:06:43 2011 multiplying 5069110 relations
Sat Oct 29 20:27:36 2011 multiply complete, coefficients have about 133.12 million bits
Sat Oct 29 20:27:37 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 20:27:37 2011 initial square root is modulo 53
Sat Oct 29 21:23:57 2011 Newton iteration failed to converge
Sat Oct 29 21:23:57 2011 algebraic square root failed
Sat Oct 29 21:23:57 2011 reading relations for dependency 10
Sat Oct 29 21:23:58 2011 read 1920899 cycles
Sat Oct 29 21:24:02 2011 cycles contain 5064278 unique relations
Sat Oct 29 21:25:16 2011 read 5064278 relations
Sat Oct 29 21:25:56 2011 multiplying 5064278 relations
Sat Oct 29 21:46:48 2011 multiply complete, coefficients have about 132.99 million bits
Sat Oct 29 21:46:48 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 21:46:49 2011 initial square root is modulo 53
Sat Oct 29 22:43:09 2011 Newton iteration failed to converge
Sat Oct 29 22:43:09 2011 algebraic square root failed
Sat Oct 29 22:43:09 2011 reading relations for dependency 11
Sat Oct 29 22:43:10 2011 read 1922664 cycles
Sat Oct 29 22:43:14 2011 cycles contain 5068604 unique relations
Sat Oct 29 22:44:27 2011 read 5068604 relations
Sat Oct 29 22:45:06 2011 multiplying 5068604 relations
Sat Oct 29 23:05:57 2011 multiply complete, coefficients have about 133.11 million bits
Sat Oct 29 23:05:58 2011 warning: no irreducible prime found, switching to small primes
Sat Oct 29 23:05:58 2011 initial square root is modulo 53
Sun Oct 30 00:02:22 2011 Newton iteration failed to converge
Sun Oct 30 00:02:22 2011 algebraic square root failed
Sun Oct 30 00:02:22 2011 reading relations for dependency 12
Sun Oct 30 00:02:22 2011 read 1922119 cycles
Sun Oct 30 00:02:26 2011 cycles contain 5064340 unique relations
Sun Oct 30 00:03:41 2011 read 5064340 relations
Sun Oct 30 00:04:21 2011 multiplying 5064340 relations
Sun Oct 30 00:25:12 2011 multiply complete, coefficients have about 132.99 million bits
Sun Oct 30 00:25:13 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 00:25:13 2011 initial square root is modulo 53
Sun Oct 30 01:21:33 2011 Newton iteration failed to converge
Sun Oct 30 01:21:33 2011 algebraic square root failed
Sun Oct 30 01:21:33 2011 reading relations for dependency 13
Sun Oct 30 01:21:34 2011 read 1923598 cycles
Sun Oct 30 01:21:38 2011 cycles contain 5068416 unique relations
Sun Oct 30 01:22:51 2011 read 5068416 relations
Sun Oct 30 01:23:30 2011 multiplying 5068416 relations
Sun Oct 30 01:44:22 2011 multiply complete, coefficients have about 133.10 million bits
Sun Oct 30 01:44:23 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 01:44:23 2011 initial square root is modulo 53
Sun Oct 30 02:40:43 2011 Newton iteration failed to converge
Sun Oct 30 02:40:43 2011 algebraic square root failed
Sun Oct 30 02:40:43 2011 reading relations for dependency 14
Sun Oct 30 02:40:44 2011 read 1922990 cycles
Sun Oct 30 02:40:48 2011 cycles contain 5066768 unique relations
Sun Oct 30 02:42:02 2011 read 5066768 relations
Sun Oct 30 02:42:41 2011 multiplying 5066768 relations
Sun Oct 30 03:03:33 2011 multiply complete, coefficients have about 133.06 million bits
Sun Oct 30 03:03:33 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 03:03:34 2011 initial square root is modulo 53
Sun Oct 30 03:59:54 2011 reading relations for dependency 15
Sun Oct 30 03:59:55 2011 read 1923933 cycles
Sun Oct 30 03:59:59 2011 cycles contain 5068060 unique relations
Sun Oct 30 04:01:18 2011 read 5068060 relations
Sun Oct 30 04:01:57 2011 multiplying 5068060 relations
Sun Oct 30 04:22:51 2011 multiply complete, coefficients have about 133.09 million bits
Sun Oct 30 04:22:52 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 04:22:52 2011 initial square root is modulo 53
Sun Oct 30 05:19:10 2011 Newton iteration failed to converge
Sun Oct 30 05:19:10 2011 algebraic square root failed
Sun Oct 30 05:19:10 2011 reading relations for dependency 16
Sun Oct 30 05:19:11 2011 read 1923668 cycles
Sun Oct 30 05:19:15 2011 cycles contain 5068872 unique relations
Sun Oct 30 05:20:28 2011 read 5068872 relations
Sun Oct 30 05:21:07 2011 multiplying 5068872 relations
Sun Oct 30 05:41:58 2011 multiply complete, coefficients have about 133.11 million bits
Sun Oct 30 05:41:59 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 05:41:59 2011 initial square root is modulo 53
Sun Oct 30 06:38:18 2011 Newton iteration failed to converge
Sun Oct 30 06:38:18 2011 algebraic square root failed
Sun Oct 30 06:38:18 2011 reading relations for dependency 17
Sun Oct 30 06:38:19 2011 read 1921938 cycles
Sun Oct 30 06:38:23 2011 cycles contain 5065234 unique relations
Sun Oct 30 06:39:37 2011 read 5065234 relations
Sun Oct 30 06:40:16 2011 multiplying 5065234 relations
Sun Oct 30 07:01:06 2011 multiply complete, coefficients have about 133.01 million bits
Sun Oct 30 07:01:07 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 07:01:07 2011 initial square root is modulo 53
Sun Oct 30 07:57:23 2011 Newton iteration failed to converge
Sun Oct 30 07:57:23 2011 algebraic square root failed
Sun Oct 30 07:57:23 2011 reading relations for dependency 18
Sun Oct 30 07:57:24 2011 read 1920749 cycles
Sun Oct 30 07:57:28 2011 cycles contain 5065534 unique relations
Sun Oct 30 07:58:42 2011 read 5065534 relations
Sun Oct 30 07:59:21 2011 multiplying 5065534 relations
Sun Oct 30 08:20:12 2011 multiply complete, coefficients have about 133.02 million bits
Sun Oct 30 08:20:13 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 08:20:13 2011 initial square root is modulo 53
Sun Oct 30 09:16:32 2011 Newton iteration failed to converge
Sun Oct 30 09:16:32 2011 algebraic square root failed
Sun Oct 30 09:16:32 2011 reading relations for dependency 19
Sun Oct 30 09:16:33 2011 read 1921228 cycles
Sun Oct 30 09:16:38 2011 cycles contain 5063624 unique relations
Sun Oct 30 09:17:51 2011 read 5063624 relations
Sun Oct 30 09:18:31 2011 multiplying 5063624 relations
Sun Oct 30 09:39:22 2011 multiply complete, coefficients have about 132.97 million bits
Sun Oct 30 09:39:23 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 09:39:23 2011 initial square root is modulo 53
Sun Oct 30 10:35:42 2011 Newton iteration failed to converge
Sun Oct 30 10:35:42 2011 algebraic square root failed
Sun Oct 30 10:35:42 2011 reading relations for dependency 20
Sun Oct 30 10:35:43 2011 read 1922751 cycles
Sun Oct 30 10:35:47 2011 cycles contain 5064916 unique relations
Sun Oct 30 10:37:02 2011 read 5064916 relations
Sun Oct 30 10:37:42 2011 multiplying 5064916 relations
Sun Oct 30 10:58:33 2011 multiply complete, coefficients have about 133.01 million bits
Sun Oct 30 10:58:34 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 10:58:35 2011 initial square root is modulo 53
Sun Oct 30 11:54:54 2011 Newton iteration failed to converge
Sun Oct 30 11:54:54 2011 algebraic square root failed
Sun Oct 30 11:54:54 2011 reading relations for dependency 21
Sun Oct 30 11:54:55 2011 read 1922658 cycles
Sun Oct 30 11:54:59 2011 cycles contain 5067126 unique relations
Sun Oct 30 11:56:13 2011 read 5067126 relations
Sun Oct 30 11:56:52 2011 multiplying 5067126 relations
Sun Oct 30 12:17:44 2011 multiply complete, coefficients have about 133.06 million bits
Sun Oct 30 12:17:45 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 12:17:45 2011 initial square root is modulo 53
Sun Oct 30 13:14:04 2011 Newton iteration failed to converge
Sun Oct 30 13:14:04 2011 algebraic square root failed
Sun Oct 30 13:14:04 2011 reading relations for dependency 22
Sun Oct 30 13:14:06 2011 read 1922046 cycles
Sun Oct 30 13:14:10 2011 cycles contain 5065688 unique relations
Sun Oct 30 13:15:25 2011 read 5065688 relations
Sun Oct 30 13:16:04 2011 multiplying 5065688 relations
Sun Oct 30 13:36:56 2011 multiply complete, coefficients have about 133.02 million bits
Sun Oct 30 13:36:57 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 13:36:57 2011 initial square root is modulo 53
Sun Oct 30 14:33:17 2011 Newton iteration failed to converge
Sun Oct 30 14:33:17 2011 algebraic square root failed
Sun Oct 30 14:33:17 2011 reading relations for dependency 23
Sun Oct 30 14:33:18 2011 read 1921561 cycles
Sun Oct 30 14:33:22 2011 cycles contain 5065824 unique relations
Sun Oct 30 14:34:36 2011 read 5065824 relations
Sun Oct 30 14:35:16 2011 multiplying 5065824 relations
Sun Oct 30 14:56:07 2011 multiply complete, coefficients have about 133.03 million bits
Sun Oct 30 14:56:08 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 14:56:08 2011 initial square root is modulo 53
Sun Oct 30 15:52:24 2011 Newton iteration failed to converge
Sun Oct 30 15:52:24 2011 algebraic square root failed
Sun Oct 30 15:52:24 2011 reading relations for dependency 24
Sun Oct 30 15:52:26 2011 read 1922653 cycles
Sun Oct 30 15:52:30 2011 cycles contain 5068270 unique relations
Sun Oct 30 15:53:43 2011 read 5068270 relations
Sun Oct 30 15:54:23 2011 multiplying 5068270 relations
Sun Oct 30 16:15:14 2011 multiply complete, coefficients have about 133.10 million bits
Sun Oct 30 16:15:14 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 16:15:15 2011 initial square root is modulo 53
Sun Oct 30 17:11:31 2011 Newton iteration failed to converge
Sun Oct 30 17:11:31 2011 algebraic square root failed
Sun Oct 30 17:11:31 2011 reading relations for dependency 25
Sun Oct 30 17:11:32 2011 read 1923008 cycles
Sun Oct 30 17:11:36 2011 cycles contain 5067092 unique relations
Sun Oct 30 17:12:50 2011 read 5067092 relations
Sun Oct 30 17:13:30 2011 multiplying 5067092 relations
Sun Oct 30 17:34:20 2011 multiply complete, coefficients have about 133.06 million bits
Sun Oct 30 17:34:21 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 17:34:21 2011 initial square root is modulo 53
Sun Oct 30 18:30:37 2011 Newton iteration failed to converge
Sun Oct 30 18:30:37 2011 algebraic square root failed
Sun Oct 30 18:30:37 2011 reading relations for dependency 26
Sun Oct 30 18:30:38 2011 read 1921717 cycles
Sun Oct 30 18:30:42 2011 cycles contain 5064030 unique relations
Sun Oct 30 18:31:56 2011 read 5064030 relations
Sun Oct 30 18:32:36 2011 multiplying 5064030 relations
Sun Oct 30 18:53:26 2011 multiply complete, coefficients have about 132.98 million bits
Sun Oct 30 18:53:26 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 18:53:27 2011 initial square root is modulo 53
Sun Oct 30 19:49:44 2011 Newton iteration failed to converge
Sun Oct 30 19:49:44 2011 algebraic square root failed
Sun Oct 30 19:49:44 2011 reading relations for dependency 27
Sun Oct 30 19:49:45 2011 read 1920575 cycles
Sun Oct 30 19:49:50 2011 cycles contain 5062388 unique relations
Sun Oct 30 19:51:05 2011 read 5062388 relations
Sun Oct 30 19:51:44 2011 multiplying 5062388 relations
Sun Oct 30 20:12:34 2011 multiply complete, coefficients have about 132.94 million bits
Sun Oct 30 20:12:35 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 20:12:35 2011 initial square root is modulo 53
Sun Oct 30 21:08:53 2011 reading relations for dependency 28
Sun Oct 30 21:08:54 2011 read 1922721 cycles
Sun Oct 30 21:08:58 2011 cycles contain 5067978 unique relations
Sun Oct 30 21:10:11 2011 read 5067978 relations
Sun Oct 30 21:10:51 2011 multiplying 5067978 relations
Sun Oct 30 21:31:43 2011 multiply complete, coefficients have about 133.09 million bits
Sun Oct 30 21:31:44 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 21:31:44 2011 initial square root is modulo 53
Sun Oct 30 22:28:07 2011 Newton iteration failed to converge
Sun Oct 30 22:28:07 2011 algebraic square root failed
Sun Oct 30 22:28:07 2011 reading relations for dependency 29
Sun Oct 30 22:28:08 2011 read 1924199 cycles
Sun Oct 30 22:28:12 2011 cycles contain 5069314 unique relations
Sun Oct 30 22:29:27 2011 read 5069314 relations
Sun Oct 30 22:30:07 2011 multiplying 5069314 relations
Sun Oct 30 22:50:59 2011 multiply complete, coefficients have about 133.12 million bits
Sun Oct 30 22:51:00 2011 warning: no irreducible prime found, switching to small primes
Sun Oct 30 22:51:00 2011 initial square root is modulo 53
Sun Oct 30 23:47:21 2011 Newton iteration failed to converge
Sun Oct 30 23:47:21 2011 algebraic square root failed
Sun Oct 30 23:47:21 2011 reading relations for dependency 30
Sun Oct 30 23:47:22 2011 read 1923086 cycles
Sun Oct 30 23:47:26 2011 cycles contain 5068548 unique relations
Sun Oct 30 23:48:41 2011 read 5068548 relations
Sun Oct 30 23:49:21 2011 multiplying 5068548 relations
Mon Oct 31 00:10:14 2011 multiply complete, coefficients have about 133.10 million bits
Mon Oct 31 00:10:15 2011 warning: no irreducible prime found, switching to small primes
Mon Oct 31 00:10:15 2011 initial square root is modulo 53
Mon Oct 31 01:06:36 2011 Newton iteration failed to converge
Mon Oct 31 01:06:36 2011 algebraic square root failed
Mon Oct 31 01:06:36 2011 reading relations for dependency 31
Mon Oct 31 01:06:38 2011 read 1921195 cycles
Mon Oct 31 01:06:42 2011 cycles contain 5064628 unique relations
Mon Oct 31 01:07:57 2011 read 5064628 relations
Mon Oct 31 01:08:36 2011 multiplying 5064628 relations
Mon Oct 31 01:29:28 2011 multiply complete, coefficients have about 133.00 million bits
Mon Oct 31 01:29:29 2011 warning: no irreducible prime found, switching to small primes
Mon Oct 31 01:29:29 2011 initial square root is modulo 53
Mon Oct 31 02:25:50 2011 Newton iteration failed to converge
Mon Oct 31 02:25:50 2011 algebraic square root failed
Mon Oct 31 02:25:50 2011 reading relations for dependency 32
Mon Oct 31 02:25:52 2011 read 1921864 cycles
Mon Oct 31 02:25:56 2011 cycles contain 5066216 unique relations
Mon Oct 31 02:27:10 2011 read 5066216 relations
Mon Oct 31 02:27:50 2011 multiplying 5066216 relations
Mon Oct 31 02:48:42 2011 multiply complete, coefficients have about 133.04 million bits
Mon Oct 31 02:48:43 2011 warning: no irreducible prime found, switching to small primes
Mon Oct 31 02:48:43 2011 initial square root is modulo 53
Mon Oct 31 03:45:02 2011 Newton iteration failed to converge
Mon Oct 31 03:45:02 2011 algebraic square root failed
Mon Oct 31 03:45:02 2011 reading relations for dependency 33
Mon Oct 31 03:45:03 2011 read 1921618 cycles
Mon Oct 31 03:45:07 2011 cycles contain 5065538 unique relations
Mon Oct 31 03:46:21 2011 read 5065538 relations
Mon Oct 31 03:47:01 2011 multiplying 5065538 relations
Mon Oct 31 04:07:53 2011 multiply complete, coefficients have about 133.02 million bits
Mon Oct 31 04:07:54 2011 warning: no irreducible prime found, switching to small primes
Mon Oct 31 04:07:54 2011 initial square root is modulo 53
Mon Oct 31 05:04:17 2011 sqrtTime: 154886
Mon Oct 31 05:04:17 2011 prp46 factor: 1359529908141779271184277189171489400662097997
Mon Oct 31 05:04:17 2011 prp62 factor: 19118743959352360640255932415783896280282870589357747809888407
Mon Oct 31 05:04:17 2011 prp113 factor: 96085074907904278299947619547631473717883403021818589315152706842120055325258281894963227008240264378713088470181
Mon Oct 31 05:04:17 2011 elapsed time 64:20:38

225 digit prime has only 209 digits

The remarkable 1,000+ bit factorization of the large composite cofactor of 21031-1 gives the factors as p74 * p225. It was reported on the NFS Discussion board on Aug 9, 2011.

Here is the text:

The composite cofactor of 2,1031- was the product of 74-digit and 225-digit prime numbers:
74-digit prime factor:
 85884311010746784399233543419755720548350735429670484635313607293408440231
225-digit prime factor:
 2608126619512734023079871401658597171708499248629287812371858820458873848148365066692974001408079\
 0094023694008624928430905568835328503742450614946289860645017638349124175799945515756962732171253\
 365651516226751
This is the project's first kilobit SNFS factorization. The factors will be reported to the Cunningham
project and will be recorded on Page 122.

Unfortunately, this is not correct. The large number above has only 209 digits.

The 225-digit prime should be:

N = 2982096305018115260812661951273402307987140165859717170849924862928781237185
88204588738481483650666929740014080790094023694008624928430905568835328503742450
614946289860645017638349124175799945515756962732171253365651516226751

A Copy & Paste slip, no doubt.

[ The Forum entry has now been corrected by the author, after a quick email ] 

UBASIC – Millennium Bug Fixed – At Last

UBASIC is a marvellous BASIC-like system using high-precision arithmetic, written by Prof. Yuji Kida of Japan.

However, the date function produces CCYY for the year where CC is the century but YY is the 2-digit year with a leading blank!

For example, in 2009 we saw:

Words for long variables 540 (Words for internal calculation 540)
Free text area = 39655 bytes
OK
print date
20 9/12/30/ 9:22:08
OK

But finally, in 2010, it is now fixed:

print date
2010/ 1/25/ 0:19:55
OK

And it only took 10 years! 🙂

C241 The Results

The factors of the composite 241-digit number from (16·10241-7)/9 = 17241 = 17 · C241 have finally emerged. They are three primes with 65-digits, 66-digits and 111-digits respectively:

p65=270337860498008194082459267955\
20615358719149908036271396619108987

p66=122051692513357047795460444698\
080453043250398905366859681372244889 and

p111=316940598147621047292107747704\
251800926330158032587268989314\
536704792625367268739179292577\
795143793534075784267

Whew !

C241 New Lanczos Time – 357 Hours

After advice from Serge Batalov, I stopped the Lanczos run on the 241-digit composite number and did five more days of sieving with GGNFS. This increased the raw relation count from about 102 M to nearly 116 M.

...
Fri Dec 18 17:45:40 2009  found 23488388 hash collisions in 115930392 relations
Fri Dec 18 17:45:55 2009  commencing duplicate removal, pass 2
Fri Dec 18 17:47:58 2009  found 23586813 duplicates and 92343579 unique relations
...

These extra relations enabled Msieve to reduce the matrix size from about 13.2 M down to about 11.3 M, thus considerably reducing the run-time for solution. Here is the reduced time estimate:

C241 New Lanczos Time

The new time in the Lanczos step saves 515 – 357 = 158 hours. The extra sieving took 5 days or 120 hours. That’s an overall saving of 38 hours — a grand total of a day and a half. 🙂

C241 Lanczos Time – 515 Hours

My C241 number from Makoto’s list* has finally started the Lanczos step. But at 515 hours, I won’t even get the answer this year. 🙂  I did think it would probably be a long calculation after getting past 100 million relations and producing a 13.2M x 13.2M matrix !

...
Sat Dec 12 13:27:37 2009  found 19564136 hash collisions in 102326209 relations
Sat Dec 12 13:27:52 2009  commencing duplicate removal, pass 2
Sat Dec 12 13:29:42 2009  found 19487173 duplicates and 82839036 unique relations
...

Now all we can do is wait. At least the Msieve program provides a checkpoint every 12 (?) hours so we can breathe easy. The Lanczos algorithm is equivalent to inverting a matrix – in this case solving a system of 13.2 million linear equations with 13.2 million variables. Gasp !

C241 Lanczos Time

To see the full width of the above picture, it is best viewed with a horizontal screen resolution of 1,280 or more. However, if viewing at a lower resolution and you are using Opera, just hit the “-” key a couple of times to shrink the image slightly. “*” will bring you instantly back to your normal resolution.


* This composite number is from the partial factorisation of the 242-digit number 177777… (7 repeated 241 times), or:

(16·10241-7)/9 = 17241 = 17 · C241

See the factorisation website of Makoto Kamada for other incredible results.

The 7-Pointed Magic Star Problem

#
#   Solve the 7-Pointed Magic Star Problem
#
#   Numbers 1-14 give equal sums in each of 7 lines making up
#   the star shape below.  Eg: B+C+D+E = 30, B+F+J+M = 30, etc.
#
#                 A
#
#       B     C       D    E
#
#        F                G
#     H                      I
#          J             K
#                 L
#            M         N
#
#

This is a similar problem to the 6-Pointed Magic Star Problem, below.

We now have fourteen unknowns with seven equations. Choosing seven values gives 14 x 13 x 12 x 11 x 10 x 9 x 8 (14 choices of A x 13 choices of B etc. or 17,297,280) possible solutions.

Many of these choices give values which are less than 1 or greater than 14 for some of the letters. We also must eliminate illegal combinations where some numbers are duplicated. Finally we get a total of 1,008 solutions.

Counting 7 rotations and 2 reflections as equivalent, we find that there are just (1008 / 14) or 72 unique solutions.

Here are the first few:

 N   a  b  c  d  e  f  g  h  i  j  k  l  m  n                     P V

 1:  1  2  4 10 14 13  8 12 11  6  3  7  9  5 Peak: 54 Valley: 51
 2:  1  2  5 14  9 13  7 11  8  3  4  6 12 10 Peak: 53 Valley: 52
 3:  1  2  8 14  6 11 12 10  3  4  5  9 13  7 Peak: 42 Valley: 63
 4:  1  2 10 14  4 11  6  8  9 12 13  3  5  7 Peak: 36 Valley: 69
 5:  1  2 10 14  4 13 12  6  3  8  9 11  7  5 Peak: 28 Valley: 77
 6:  1  3  5 13  9 10 12 14  4  6  7  8 11  2 Peak: 44 Valley: 61
 7:  1  3  6 14  7 12 10 11  5  2  4  8 13  9 Peak: 49 Valley: 56
 8:  1  3  8 13  6  7 12 14  4  9 10  5 11  2 Peak: 41 Valley: 64
 9:  1  3  9 14  4 12 13  8  2  5  7 11 10  6 Peak: 34 Valley: 71
10:  1  3 11 14  2 13  7  5  8 10 12  6  4  9 Peak: 32 Valley: 73
11:  1  3 11 14  2 13  9  5  6 10 12  8  4  7 Peak: 28 Valley: 77
12:  1  4  5 12  9 13  3 11 14  7  8  2  6 10 Peak: 55 Valley: 50
13:  1  4  6  8 12 10  7 13 14  5  2  3 11  9 Peak: 64 Valley: 41
14:  1  4  7 14  5 12 13 10  2  6  9 11  8  3 Peak: 33 Valley: 72
....

This time there are no solutions where the Peak or Valley sums are equal to 30.

[ Peak Sum = A + E + I + N + M + H + B, Valley Sum = D + G + K + L + J + F + C ]