123

C, 0.026119s (Mar 12 2016) #include <math.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define cache_size 16384 #define Phi_prec_max (47 * a) #define bit(k) (1ULL << ((k) & 63)) #define word(k) sieve[(k) >> 6] #define sbit(k) ((word(k >> 1) >...


80

Algebra, graph theory, Möbius inversion, research, and Java The symmetry group of the hexagon is the dihedral group of order 12, and is generated by a 60 degree rotation and a mirror flip across a diameter. It has 16 subgroups, but some of them are in non-trivial conjugacy groups (the ones which only have reflections have 3 choices of axis), so there are 10 ...


76

Python2.7 + Numpy 1.8.1: 10.242 s Fortran 90+: 0.029 s 0.003 s 0.022 s 0.010 s Damn straight you lost your bet! Not a drop of parallelization here too, just straight Fortran 90+. EDIT I've taken Guy Sirton's algorithm for permuting the array S (good find :D). I apparently also had the -g -traceback compiler flags active which were slowing this code down ...


69

Python 2.7 - 0.882s 0.283s (OP's original: 6.404s) Edit: Steven Rumbalski's optimization by precomputing F values. With this optimization cpython beats pypy's 0.365s. import itertools import operator import random n=6 iters = 1000 firstzero = 0 bothzero = 0 choicesF = filter(any, itertools.product([-1, 0, 0, 1], repeat=n)) for S in itertools.product([-...


62

C++ bit magic 0.84ms with simple RNG, 1.67ms with c++11 std::knuth 0.16ms with slight algorithmic modification (see edit below) The python implementation runs in 7.97 seconds on my rig. So this is 9488 to 4772 times faster depending on what RNG you choose. #include <iostream> #include <bitset> #include <random> #include <chrono> #...


59

Python (w/ PyPy JIT v1.9) ~1.9s Using a Multiple Polynomial Quadratic Sieve. I took this to be a code challenge, so I opted not to use any external libraries (other than the standard log function, I suppose). When timing, the PyPy JIT should be used, as it results in timings 4-5 times faster than that of cPython. Update (2013-07-29): Since originally ...


45

Rust: 0.011s Original Python: 8.3 A straight translation of the original Python. extern crate rand; use rand::Rng; static N: uint = 6; static ITERS: uint = 1000; fn convolve<T: Num>(into: &mut [T], a: &[T], b: &[T]) { // we want `a` to be the longest array if a.len() < b.len() { convolve(into, b, a); return ...


39

C++ (VS 2012) - 0.026s 0.015s Python 2.7.6/Numpy 1.8.1 - 12s Speedup ~x800. The gap would be a lot smaller if the convolved arrays were very large... #include <vector> #include <iostream> #include <ctime> using namespace std; static unsigned int seed = 35; int my_random() { seed = seed*1664525UL + 1013904223UL; // numerical ...


33

Mini-Flak, 6851113 cycles The program (literally) I know most people aren't likely expecting a Mini-Flak quine to be using unprintable characters and even multi-byte characters (making the encoding relevant). However, this quine does, and the unprintables, combined with the size of the quine (93919 characters encoded as 102646 bytes of UTF-8), make it ...


25

C99/C++, 8.9208s (28 Feb 2016) #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> uint64_t popcount( uint64_t v ) { v = (v & 0x5555555555555555ULL) + ((v>>1) & 0x5555555555555555ULL); v = (v & 0x3333333333333333ULL) + ((v>>2) & ...


24

Python A closed-form formula of p(n) is An exponential generating function of p(n) is where I_0(x) is the modified Bessel function of the first kind. Edit on 2015-06-11: - updated the Python code. Edit on 2015-06-13: - added a proof of the above formula. - fixed the time_limit. - added a PARI/GP code. Python def solve(): # straightforward ...


21

Python ~451 digits This is part of the library I wrote for a semiprime factorization problem, with unnecessary functions removed. It uses the Baillie-PSW primality test, which is technically a probabilistic test, but to date, there are no known pseudoprimes – and there's even a cash reward if you're able to find one (or for supplying a proof that none ...


21

C Takes 0.015s on my machine, with OP's original code taking ~ 7.7s. Tried to optimize by generating the random array and convolving in the same loop, but it doesn't seem to make a lot of difference. The first array is generated by taking an integer, write it out in binary, and change all 1 to -1 and all 0 to 1. The rest should be very straightforward. ...


21

Python 2.7 on PyPy, {2404}3{1596} (~10^4000) ...


20

Nimrod (N=22) import math, locks const N = 20 M = N + 1 FSize = (1 shl N) FMax = FSize - 1 SStep = 1 shl (N-1) numThreads = 16 type ZeroCounter = array[0..M-1, int] ComputeThread = TThread[int] var leadingZeros: ZeroCounter lock: TLock innerProductTable: array[0..FMax, int8] proc initInnerProductTable = for i in 0..FMax: ...


19

Python, n≈108 def magic_sequences(n): if n==4: return (1, 2, 1, 0),(2, 0, 2, 0) elif n==5: return (2, 1, 2, 0, 0), elif n>=7: return (n-4,2,1)+(0,)*(n-7)+(1,0,0,0), else: return () This uses the fact, which I'll prove, that the only Magic sequences of length n are: [1, 2, 1, 0] and [2, 0, 2, 0] for n=4 [...


17

J I don't expect to beat out any compiled languages, and something tells me it'd take a miraculous machine to get less than 0.09 s with this, but I'd like to submit this J anyway, because it's pretty slick. NB. constants num =: 6 iters =: 1000 NB. convolve NB. take the multiplication table */ NB. then sum along the NE-SW diagonals ...


17

Perl - 9.3X faster...830% improvement On my ancient netbook, the OP's code takes 53 seconds to run; Alistair Buxton's version takes about 6.5 seconds, and the following Perl version takes about 5.7 seconds. use v5.10; use strict; use warnings; use Algorithm::Combinatorics qw( variations_with_repetition ); use List::Util qw( any sum ); use List::MoreUtils ...


16

C++ x150 x450 x530 Instead of array I used bits (and dark magic). Thanks @ace for the faster random function. How does it work: the first 15th bits of the integer s represent the array S[15]; the zeroes represent -1, the ones represent +1. The array F is build in a similar way. But with two bit for each symbol. 00 represent -1 01 and 10 represent 0 11 ...


16

128,673,515 cycles Try it online Explanation The reason that Miniflak quines are destined to be slow is Miniflak's lack of random access. To get around this I create a block of code that takes in a number and returns a datum. Each datum represents a single character like before and the main code simply queries this block for each one at a time. This ...


15

Stolen wholesale from Bit twiddling hacks: uint8_t f(uint32_t v) { static const uint8_t MultiplyDeBruijnBitPosition2[32] = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; return MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27]; }


15

C99 - 3x3 board in 0.084s Edit: I refactored my code and did some deeper analysis on the results. Further Edits: Added pruning by symmetries. This makes 4 algorithm configurations: with or without symmetries X with or without alpha-beta pruning Furthest Edits: Added memoization using a hash table, finally achieving the impossible: solving a 3x3 board! ...


15

C Introduction As commented by David Carraher, the simplest way of analysing the hexagon tiling seemed to be to take advantage of its isomorphism with the 3 dimensional Young Diagram, essentially an x,y square filled with integer height bars whose z heights must stay the same or increase as the z axis is approached. I started with an algorithm for finding ...


15

C++ No more naive approach. Only evaluate inside the ellipsoid. Uses the armadillo, ntl, gsl and pthread libraries. Install using apt-get install libarmadillo-dev libntl-dev libgsl-dev Compile the program using something like: g++ -Wall -std=c++11 -O3 -fno-math-errno -funsafe-math-optimizations -ffast-math -fno-signed-zeros -fno-trapping-math -fomit-...


14

Nimrod: ~38,667 (580,000,000/15,000) This answer uses a pretty simple approach. The code employs a simple prime number sieve that stores the prime of the smallest prime power in each slot for composite numbers (zero for primes), then uses dynamic programming to construct the totient function over the same range, then sums the results. The program spends ...


14

gcc C++ n ≈ 36 (57 seconds on my system) Uses Glynn formula with a Gray code for updates if all column sums are even, otherwise uses Ryser's method. Threaded and vectorized. Optimized for AVX, so don't expect much on older processors. Don't bother with n>=35 for a matrix with only +1's even if your system is fast enough since the signed 128 bit ...


14

Haskell import Control.Parallel.Strategies import qualified Data.Vector.Unboxed as V import qualified Data.Vector as VB type Poly = V.Vector Int type Matrix = VB.Vector ( VB.Vector Poly ) constpoly :: Int -> Int -> Poly constpoly n c = V.generate (n+1) (\i -> if i==0 then c else 0) add :: Poly -> Poly -> Poly add = V.zipWith (+) ...


14

C++ (GCC) + x86 assembly, score 32 36 62 in 259 seconds (official) Results computed so far. My computer runs out of memory after 65. 1 2 2 23 3 235 4 2357 5 112357 6 113257 7 1131725 8 113171925 9 1131719235 10 113171923295 11 113171923295 12 1131719237295 13 11317237294195 14 1131723294194375 15 113172329419437475 16 1131723294194347537 17 ...


13

C++ up to N=6 3x3 answer 3: 111 000 000 4x4 answer 10: 1110 0010 1100 0000 5x5 answer 52: 11010 10000 11011 10100 00000 6x6 ...


13

C++ bit magic ~16ms multithreaded, 56ms singlethreaded. ~4000 speedup. (speedup is based on multithreaded code on my i7-2820QM and the 1 min 9 seconds mentioned in the question. Since the OP's system has worse single threaded performance than my CPU but better multi threaded perfiormance i expect this number to be accurate) The multithreaded part is quite ...


Only top voted, non community-wiki answers of a minimum length are eligible