Strange number 123456

To exclude I/O from this post I've modified code. So now it not only calculates factorials but also sums their digits and at last sums the sums of digits and as a result there's on one I/O operation. Lisp as usual behaving quite good. And a result of this code:

	(defun factorial (n)
	(defun i_factorial (k acc)
	(if (= 0 k)
	acc
	(i_factorial (- k 1) (* k acc))))
	(i_factorial n 1))
	(defun digits (n)
	(defun i_digits (k acc)
	(if (= 0 k)
	acc
	(i_digits (truncate k 10) (cons (mod k 10) acc))))
	(i_digits n '()))
	(defun digits_s (n)
	(mapcar
	#'(lambda (k) (parse-integer (string k)))
	(coerce (write-to-string n) 'list)))
	(format T "~D~%"
	(time (reduce
	'+
	(mapcar
	#'(lambda (n)
	(reduce
	'+
	(digits_s (factorial n))))
	'(1 12 123 1234 12345 123456)))))

view raw test.lisp hosted with ❤ by GitHub

is

Evaluation took:
  7.762 seconds of real time
  7.565354 seconds of total run time (7.363660 user, 0.201694 system)
  [ Run times consist of 0.399 seconds GC time, and 7.167 seconds non-GC time. ]
  97.46% CPU
  17,812,436,719 processor cycles
  177 page faults
  15,624,347,568 bytes consed
  
2652733

Almost similar results I've got from Go program:

	package main
	import (
	"fmt"
	"math/big"
	"strings"
	"strconv"
	"time"
	)
	func Factorial(n *big.Int) *big.Int {
	var unit = big.NewInt(1)
	var acc *big.Int = big.NewInt(1)
	var t = n
	for t.Cmp(unit) == 1 {
	acc.Mul(acc, t)
	t.Sub(t, unit)
	}
	return acc
	}
	func SumDigits(n string) int64 {
	var r int64
	l := strings.Split(n, "")
	for i := 0; i < len(l); i++ {
	d, _ := strconv.ParseInt(l[i], 10, 0)
	r += d
	}
	return r
	}
	func main() {
	var s int64 = 0
	t1 := time.Now()
	n := []int64{1, 12, 123, 1234, 12345, 123456}
	for i := 0; i < len(n); i++ {
	r := Factorial(big.NewInt(n[i]))
	s += SumDigits(r.String())
	}
	t2 := time.Now()
	fmt.Printf("Elapsed time: %v\n", t2.Sub(t1))
	fmt.Println(s)
	}

view raw test.go hosted with ❤ by GitHub

Elapsed time: 4.509443s
2652733

But strangely Clojure, Haskell and Julia have got some very strange behavior. Till 12345! everything seems to be ok (though for Clojure it takes almost 1.5 sec to calculate while Lisp done it in 0.091 seconds of real time). But when we get 123456! Clojure needs almost 1 minute, Haskell and Julia just plainly refused to calculate. Even in case of Julia it was not so plainly cause it decided to eat almost all memory.

Euler #125

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 62 + 72 + 82 + 92 + 102 + 112 + 122...

	#!/usr/bin/env python
	from math import sqrt, floor
	N = 100000000
	def is_palindrome(n):
	return str(n) == str(n)[::-1]
	def sum_list(n):
	res = set()
	for i in xrange(n - 1, 0, -1):
	l = [x*x for x in xrange(i, n + 1)]
	t = sum(l)
	if t > N:
	break
	if is_palindrome(t):
	res.add(t)
	return list(res)
	if __name__ == '__main__':
	t = int(sqrt(N/2)) + 1
	l = [item for sublist in map(sum_list, xrange(2, t + 1)) for item in sublist]
	print len(set(l)), sum(set(l))

view raw euler125.py hosted with ❤ by GitHub

What's wrong with the code?

Decided to take naive implementation of factorial in Racket and Lisp:

	#lang racket
	(define (factorial n)
	(define (i_factorial n acc)
	(if (= 0 n)
	acc
	(i_factorial (- n 1) (* n acc))))
	(i_factorial n 1))
	(map (lambda (n)
	(printf "~a~n" (factorial n))) (list 1 12 123 1234 12345))

view raw factorial.rkt hosted with ❤ by GitHub

and

	(defun factorial (n)
	(defun i_factorial (n acc)
	(if (= 0 n)
	acc
	(i_factorial (- n 1) (* acc n))))
	(i_factorial n 1))
	(defun print-factorial (n)
	(format T "~D~%" (factorial n)))
	(mapcar 'print-factorial '(1 12 123 1234 12345))

view raw factorial.lisp hosted with ❤ by GitHub

And even after

raco exe test.rkt

timing is as follows:

raco exe test.rkt
time ./test

real 0m0.697s
user 0m0.581s
sys 0m0.092s

time sbcl --script test.lisp

real 0m0.139s
user 0m0.085s
sys 0m0.049s

Maybe I/O in Racket is rather slow?

Euler #87

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

	#!/usr/bin/env python
	from libeuler import primes
	if __name__ == '__main__':
	p = primes(7100)
	res = set()
	for s in p:
	for c in p:
	for q in p:
	n = s*s + c*c*c + q*q*q*q
	if n < 50000000:
	res.add(n)
	print len(res)

view raw euler87.py hosted with ❤ by GitHub