Learning Clojure

Search This Blog

Friday, December 3, 2021

A Festive Theorem

#!/usr/bin/env clojure

;; A Festive Theorem

;; About a week ago, a friend of mine who is not noted for his interest in pure mathematics, and
;; whose identity I will conceal behind the alias "Sipper" caught me in the Wetherspoons and showed
;; me a number theory proof (or at least most of one, we couldn't actually finish the argument off)

;; I've never been interested in number theory. It seems both useless and boring, but the central
;; idea of this proof was intriguing, so today I sat down, again in Wetherspoons, with quite a lot
;; of paper and coffee and an all-day brunch (all for £7.30, I love Spoons, if you want to advertise
;; on this blog just get in touch), and hammered the damned thing out until I was happy with it.

;; The proof's really visual and beautiful, but not constructive, but it suggested an algorithm to
;; me, so I'm going to try to get that algorithm working, and then show why it works by visualizing
;; what it's doing.

;; I have no idea whether anyone will find this interesting, but since it's the only thing in all of
;; number theory that's ever struck me as worth knowing, and Sips found it interesting too, I'm going
;; to write it up.

;; In this first bit, a statement of the Theorem, which itself took me a while to get my head round.

;; make the repl stop after the first 20 elements of a sequence
(set! *print-length* 20)

;; If you square an even number, then it will be divisible by 4
;; But if you square an odd number, then it will leave a residue of 1 mod 4

(defn square [x] (* x x))
(def mod4 #(rem % 4))

(map mod4 (map square (range)))  ;; (0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 ...)

;; If that's not obvious, think about it for a few minutes and see whether you can make it so....

;; This means that if you take an even and an odd number, and square them, and add the squares, then
;; the residue mod 4 will always be 1

(mod4 (+ (square 2)  (square 5)))     ;; 1    ( 2*2 + 5*5 = 29 = 28 + 1 = 4 * 7 + 1)
(mod4 (+ (square 10) (square 17)))    ;; 1    (etc)

;; Let's check this is actually true for lots of numbers:

(def naturals (map inc (range))) ;; (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...)

(defn odd [n] (- (* 2 n) 1))
(def odds (map odd naturals))   ;; (1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ...)

(defn even [n] (* 2 n))
(def evens (map even naturals)) ;; (2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 ...)

;; Here are all possible pairs of natural numbers
(def pairs (for [sum naturals i (take (dec sum) naturals)] (list i, (- sum i)))) ;; ((1 1) (1 2) (2 1) (1 3) (2 2) (3 1) (1 4) (2 3) (3 2) (4 1) (1 5) (2 4) (3 3) (4 2) (5 1) (1 6) (2 5) (3 4) (4 3) (5 2) ...)

;; From which we can construct all odd-even pairs
(def odd-even-pairs (for [[i,j] pairs] (list (odd i) (even j)))) ;; ((1 2) (1 4) (3 2) (1 6) (3 4) (5 2) (1 8) (3 6) (5 4) (7 2) (1 10) (3 8) (5 6) (7 4) (9 2) (1 12) (3 10) (5 8) (7 6) (9 4) ...)

;; From which we can construct all sums of squares of odd and even numbers
(def odd-even-squares (for [[i,j] odd-even-pairs] (+ (square i) (square j)))) ;;(5 17 13 37 25 29 65 45 41 53 101 73 61 65 85 145 109 89 85 97 ...)

;; paranoid check, if I did that right they should all be 1 mod 4
(map mod4 odd-even-squares) ;; (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...)


;; So, since both : it's obvious ; and also it looks like it might actually be true, I think we can take it to the bank that:

;; If o is an odd number, and e is an even number, then o*o+e*e is 1 mod 4

;; This has apparently been pretty obvious to everyone who's ever thought about it, and is just one
;; of those number-theory facts that always seem to fascinate people who aren't me.

;; But it occurred to Albert Girard in 1632 to wonder if the converse was true:

;; If you have a number that is 1 mod 4, can you always split it into odd and even squares?

;; Let's look for counterexamples:
(def early-ones (sort (take 10000 odd-even-squares))) ;; (5 13 17 25 29 37 41 45 53 61 65 65 73 85 85 89 97 101 109 113 ...)

(def candidates (map #(+ (* 4 %) 1) naturals)) ;; (5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 ...)


;; This is such a hack, I am shame....
(require 'clojure.set)
(clojure.set/difference (set (take 100 candidates)) (set early-ones)) ;; (9 21 33 49 57 69 77 81 93 105 121 129 133 141 161 165 177 189 201 209 ...)

;; So it looks like the converse is not true.

;; 9, for instance, is 4*2+1, so it's a candidate, but it looks like you can't split it into odd and even squares.
;; Let's try by hand, just going through all the possible odd numbers

;; 9 = 1*1 + 8 ; 8 is not the square of anything
;; 9 = 3*3 + 0 ; 0 is not the square of a natural number

;; This seems a bit dodgy to me, 9 = 3 * 3 + 0 * 0, so does it work if we count 0 as an even number? This will turn out not to matter too much.....

;; Look at 21
;; 21 = 1*1 + 20 ; 20 is not the square of anything
;; 21 = 3*3 + 12 ; 12 is not the square of anything
;; 21 = 5*5 - 4  ; oops, 5*5 is too big, although it does look like 21 = 5*5 - 2*2, but that wasn't the question. Sum of squares, not difference of squares.

;; OK 33 then
;; 33 = 1*1 + 32 ; 32 is not the square of anything
;; 33 = 3*3 + 24 ; 24 is not the square of anything
;; 33 = 5*5 + 8  ;  8 is not the square of anything
;; 33 = 7*7 - 16 ; oh bloody hell, 33 = 7*7 - 4*4

;; Anyway, that's not the question. Neither 21 nor 33 are the sum of two squares., even though 21 = 5*4+1 and 33 = 4*8+1

;; Looking at the list of the ones that did work
early-ones ;; (5 13 17 25 29 37 41 45 53 61 65 65 73 85 85 89 97 101 109 113 ...)

;; One might notice that there are an awful lot of prime numbers on that list. (although they're not all primes....)

;; In fact
(defn divisors [n] (filter #(= 0 (rem n %)) (map inc (range n))))

(divisors 12) ;; (1 2 3 4 6 12)

(defn prime? [n] (= (count (divisors n)) 2))
(filter prime? (range 200)) ;; (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 ...)


(def candidate-primes (filter prime? candidates)) ;; (5 13 17 29 37 41 53 61 73 89 97 101 109 113 137 149 157 173 181 193 ...)

(clojure.set/difference (set (take 100 candidate-primes)) (set early-ones)) ;; #{}

(clojure.set/difference (set (take 1000 candidate-primes)) (set early-ones)) ;; #{}

;; If there's a prime of form 4*n+1 that isn't the sum of one odd and one even square, then it's fairly big

;; It looks as though, at least for the first thousand candidates, if a number is both prime, and of form 4*n+1,
;; then it is expressible as an even square plus an odd square.

;; Albert Girard, in 1625, presumably after a fair amount of dicking about with bits of paper,
;; conjectured that this might be so for all candidate primes.

;; On December 25th 1640, Pierre de Fermat wrote to his friend Marin Mersenne that he had proved
;; that this was true, but he did not trouble to include the proof or indeed ever tell anyone how he
;; did it.

;; On the 12th of April 1749, Leonhard Euler wrote to his friend Christian Goldbach that he had
;; proved that this was true, and then actually went and published his (intricate and difficult) proof.

;; In recognition of Fermat's invaluable contribution, this result is universally known as

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;;             Fermat's Christmas Theorem.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Let p be a prime number

;; Then p is expressible as the sum of odd and even squares
;; if and only if p is 4*n+1 for some natural number n








Thursday, December 2, 2021

A test program

#!/usr/bin/env clojure

;; It looks like clojure has become a full citizen of Debian

;; In emacs, a syntax highlighted program can be converted to html with htmlize-buffer, and then if
;; you top and tail that and copy it to blogger it comes up nicely. And this seems to still be
;; working after all this time

;; So here is my first published clojure program for a while...

;; If you're using Debian 11, you can run it by installing clojure with
;; $ sudo apt install clojure

;; saving this file as test.clj

;; and then in a terminal window making the file executable
;; $ chmod +x test.clj
;; and then running it
;; $ ./test.clj

(println "hello")

(defn factorial [n]
  (if (< n 1) 1
      (* n (factorial (- n 1)))))

(println '(factorial 10) (factorial 10))

;; If all is working then you should see something like
;; $ ./test.clj
;; hello
;; (factorial 10) 3628800

Emacs, even

The truly terrifying bit of getting any language to work on your machine is getting it to work with EMACS. 

Last time I tried to get clojure working, this was the stage that I gave up at. Everything was just broken, and so I wrote the program I was going to write in python instead.

But all it took this time was:

(Emacs 27.1, the version that comes with Debian 11/Bullseye)

M-x package install

clojure-mode

(churn)

and then I can load my test.clj program from earlier, and it's syntax highlighted. 

M-x package-list-packages

tells me that it's clojure-mode 5.13.0, from melpa-stable .

I can save the program, and run 

./test.clj 

from the command line in a terminal, and it just works, with a slightly irritating 2 second delay.

I might hope for more:

I remember once I could do things like putting the cursor in an expression and pressing Alt-Ctrl-x to evaluate that expression in a running REPL.

but this will do for now. 

I can always copy and paste things to a REPL, after all.


Clojure Shell Scripts on Debian

So I managed to install a very recent clojure through Debian's package manager, and it just worked.

And my next thought is: "If it's somehow become a proper part of Debian, does that mean I can do shell scripts?"

so

cat >test.clj

#!/usr/bin/env clojure
(print "hello")

chmod +x test.clj

./test.clj

(2 second pause...)

hello

Compare with the python equivalent:

cat >test.py

#!/usr/bin/env python
print("hello")


chmod +x test.py

./test.py
hello

The only difference is the lack of a two second pause. Python responds instantly.

I can live with a two second pause.

I am totally amazed and pleased by this. It feels much more like a proper programming language than it used to. It's too good to be true.

I wonder if we've got a command line argument parser yet.

Hello Again World (2nd December 2021) Setting Up Clojure on Debian 11

It's been a while since I've used Clojure, and I've upgraded my system a fair bit since then, so I'm going to try to start again from scratch.


My computer is running latest stable Debian

cat /etc/debian_version
11.1

(version 11.1, aka bullseye)

My first instinct is to install via the package manager:

apt search clojure

clojure/stable,now 1.10.2-1 all
  Lisp dialect for the JVM

clojure.org tells me that the latest version is 1.10.3, so the debian version will do.

sudo apt install clojure

clojure
Clojure 1.10.2
user=> 

That seems far too easy, does it work? 

First, can I do hello world at all?

user=> (print "hello")
hellonil

user=> (defn factorial [n] (if (< n 2) n (* n factorial (- n 1))))

#'user/factorial

user=> (factorial 10)
Execution error (ClassCastException) at user/factorial (REPL:1).
class user$factorial cannot be cast to class java.lang.Number (user$factorial is in unnamed module of loader clojure.lang.DynamicClassLoader @56ccd751; java.lang.Number is in module java.base of loader 'bootstrap')

Oh my God, what???

.....stares in bewildered disbelief and starts cursing Java and its pointless verbose complexity before seeing the problem and feeling silly...

user=> (defn factorial [n] (if (< n 2) n (* n (factorial (- n 1)))))
#'user/factorial
user => (factorial 10)
3628800


So that looks great, and it was very easy. Things have improved hugely since I last tried this!

I could hope for better error messages, something like 'can't multiply a number by a function' would have been more helpful.


 


 






Sunday, October 31, 2021

Contract Programmer Seeks Job in Cambridge (£500 reward)

Anyone in Cambridge need a programmer? I'll give you £500 if you can find me a job that I take.

CV at http://www.aspden.com

I make my usual promise, which I have paid out on several times:

If, within the next six months, I take a job which lasts longer than one month, and that is not obtained through an agency, then on the day the first cheque from that job cashes, I'll give £500 to the person who provided the crucial introduction.

If there are a number of people involved somehow, then I'll apportion it fairly between them. And if the timing conditions above are not quite met, or someone points me at a shorter contract which the £500 penalty makes not worth taking, then I'll do something fair and proportional anyway.

And this offer applies even to personal friends, and to old contacts whom I have not got round to calling yet, and to people who are themselves offering work, because why wouldn't it?

And obviously if I find one through my own efforts then I'll keep the money. But my word is generally thought to be good, and I have made a public promise on my own blog to this effect, so if I cheat you you can blacken my name and ruin my reputation for honesty, which is worth much more to me than £500.
 

 

 

I make the following boast:

I know all styles of programming and many languages, and can use any computer language you're likely to use as it was intended to be used.

I have a particular facility with mathematical concepts and algorithms of all kinds. I can become very interested in almost any problem which is hard enough that I can't solve it easily.

I have a deserved reputation for being able to produce heavily optimised, but nevertheless bug-free and readable code, but I also know how to hack together sloppy, bug-ridden prototypes, and I know which style is appropriate when, and how to slide along the continuum between them.

I've worked in telecoms, commercial research, banking, university research, chip design, server virtualization, university teaching, sports physics, a couple of startups, and occasionally completely alone.

I've worked on many sizes of machine. I've written programs for tiny 8-bit microcontrollers and gigantic servers, and once upon a time every IBM machine in the Maths Department in Imperial College was running my partial differential equation solvers in parallel in the background.

I'm smart and I get things done. I'm confident enough in my own abilities that if I can't do something I admit it and find someone who can.

I know what it means to understand a thing, and I know when I know something. If I understand a thing then I can usually find a way to communicate it to other people. If other people understand a thing even vaguely I can usually extract the ideas from them and work out which bits make sense.

Tuesday, February 5, 2019

The Unexpected Appearance of Schlemiel, the Painter

;; The Unexpected Appearance of Schlemiel, the Painter

;; I was doing some statistics one day, and I defined:

;; the average of a finite sequence
(defn average [sq] (/ (reduce + sq) (count sq)))

;; and the square of a number
(defn square [x] (* x x))

;; and a way of forgetting about all the fiddly little digits at the end
(defn twosf   [x]  (float (/ (Math/round (* x 100.0)) 100))) 

;; but for the variance I was a little torn between:
(defn variance-one [sq]
  (let [av (average sq)]
    (average (map #(square (- % av)) sq)))) 
 
;; and 
 
(defn variance-two [sq]
  (let [sqdiff #(square (- % (average sq)))]
    (average (map  sqdiff sq))))

;; and (I have a regrettable weakness for the terse...) 
(defn variance-one-liner [sq] (average (map #(square (- % (average sq))) sq)))

;; but I was surprised when I noticed this: 

(let [s (repeatedly 1000 #(rand))]
  (twosf (reduce + s)) ;; just to force the sequence to be generated before timing things
  [(time (twosf (reduce + s)))
   (time (twosf (average  s)))
   (time (twosf (variance-one s)))
   (time (twosf (variance-two s)))
   (time (twosf (variance-one-liner s)))])

;; "Elapsed time: 0.535715 msecs"
;; "Elapsed time: 0.834523 msecs"
;; "Elapsed time: 1.417108 msecs"
;; "Elapsed time: 251.650722 msecs"
;; "Elapsed time: 248.196331 msecs"
;; [496.83 0.5 0.09 0.09 0.09]


;; It seems that all these functions are correct, in the sense that they are producing
;; correct-looking answers, and yet one of them is orders of magnitude faster.

;; What is going on here, and why?

Followers