Thursday, May 30, 2013

Project Euler #70: Totient permutation

Here is problem #70.

The problem asks to find a value for $$n$$ for which $$\phi(n)$$ is a permutation of the digits of $$n$$, and for which $$n/\phi(n)$$ is at a minimum. A brief refresher of what the totient function is might be helpful here.

Basically (lifted right from Wikipedia):

In number theory, Euler's totient or phi function, $$\phi(n)$$ is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then $$\phi(n)$$ is the number of integers k in the range 1 ≤ k ≤ n for which $$gcd(n, k) = 1$$.

Notably, $$\phi(p) = p - 1$$ if $$p$$ is prime. This is because $$p$$ has no other divisors besides itself and 1, so all positive integers less than $$p$$ are relatively prime to it.

This gives a little insight on how to solve the problem: if $$n$$ happens to be prime, then $$n/\phi(n)$$ = $$n/(n - 1)$$, which is basically the smallest you can get that ratio to be. If it so happened that $$n$$'s digits are a permutation of $$\phi(n)$$ in that case, I'd have the winning number. With this strategy, all I would have to do is find a bunch of primes around the vicinity of $$10^8$$ and check the permutation constraint.

Unfortunately, since $$\phi(p) = p - 1$$, $$p$$ and $$\phi(p)$$ must differ by at least one digit, so that idea is out the window.

However, the ratio $$n/\phi(n)$$ also happens to be small if $$n$$ is a semi-prime (that is, if $$n$$ is the product of two primes). In this case, $$n$$ will have one or two other divisors besides $$n$$ itself (one in the case that the two primes are not distinct), so looking for semi-primes is the next best thing after looking for primes.

Having no idea where to start looking for these primes, I just started by poking around primes near $$\sqrt{10^8}$$, and testing if they had the two properties I was looking for. The following Clojure program eventually happens upon the result in less than a minute's time:

; lib/core.clj contains some general functions for calculating the integer
; square root, and for loading in a big list of pre-calculated primes.
(load-file "lib/core.clj")
(use
  '[clojure.math.combinatorics]
  '[lib.core :only (isqrt load-primes)])

(def primes
  (load-primes "../data/primes.txt"))

(def limit (int 1e7))

; Search around the radius of (sqrt 1e7)
(def ps
  (take-while #(<= % (* 2 (inc (isqrt limit)))) primes))

; Create pairs for semi-primes
(def pairs
  (combinations ps 2))

(defn permutation?
  "Returns true if a's digits are a permutation of b's."
  [a b]
  (let [digits #(sort (into [] (str %)))]
    (= (digits a) (digits b))))

(defn phi
  "Calculates the totient of a semi-prime created from p and q."
  [p q]
  (* (dec p) (dec q)))

(defn f
  "Creates a map entry of n/phi(n) -> [p q]."
  [pair]
  (let [p (first pair)
        q (second pair)
        n (* p q)]
    [(/ n (phi p q)) [p q]]))

(defn g
  "Returns true if the totient of the semi-prime generated from [p q] is a
  permutation of that semi-prime."
  [pair]
  (let [p (first pair)
        q (second pair)
        n (* p q)]
    (permutation? n (phi p q))))

; Create a map of n/phi(n) -> [p q], filtering out semi-primes who are
; larger than 1e7
(def h
  (filter #(<= (apply * (second %)) 10000000)
          (apply merge (cons {} (map f pairs)))))

(let [entry (first (drop-while #(not (g (second %))) (sort h)))
      pair (second entry)
      p (first pair)
      q (second pair)]
  (println (* p q)))

You can view the full source here.

Thursday, May 23, 2013

Project Euler #69: Totient maximum

Here is a link to problem #69. Basically this problem serves as a gentle introduction to Euler's totient function. Just by looking at the definition you can get a hint about how to solve this problem.

Note that:

$$\phi(n) = n\prod_{p|n}(1 - \dfrac{1}{p})$$

...a proof of which can be found on the wikipedia page for the totient function.

Armed with that, we can consider maximizing this value:

$$\dfrac{n}{\phi(n)} = \dfrac{1}{\prod_{p|n}(1 - \dfrac{1}{p})}$$

It is plain to see that to maximize that ratio, we have to minimize the denominator. This will happen if there are a lot of $$p_{i}$$'s and each of them are very small, so basically we can hunt for this number by taking the product of the first few primes (a concept known as the primorial) such that the product is under 1000000.

As it turns out,

$$p_{7}\# = 510510 < 1000000$$ and $$p_{8}\# = 9699690 > 1000000$$

...so the number we want is 510510.

Thursday, February 16, 2012

Java Fun: When 128 != 128

I didn't discover this, but I did think it was fun to share:

public class JavaWTF {
  public static void main(String[] args) {
    System.out.println(isSame(127, 127));  // true
    System.out.println(isSame(128, 128));  // false
  }

  private static boolean isSame(Integer i1, Integer i2) {
    return i1 == i2;
  }
}

This is still true as of JDK 1.6. Why is this so? I took a look at the bytecode to see what's going on, and here's what we have:

Compiled from "JavaWTF.java"
public class JavaWTF extends java.lang.Object{
public JavaWTF();
  Code:
   0: aload_0
   1: invokespecial #1; //Method java/lang/Object."<init>":()V
   4: return

public static void main(java.lang.String[]);
  Code:
   0: bipush  127
   2: istore_1
   3: getstatic #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   6: new #3; //class java/lang/Integer
   9: dup
   10:  iload_1
   11:  invokespecial #4; //Method java/lang/Integer."<init>":(I)V
   14:  new #3; //class java/lang/Integer
   17:  dup
   18:  iload_1
   19:  invokespecial #4; //Method java/lang/Integer."<init>":(I)V
   22:  if_acmpne 29
   25:  iconst_1
   26:  goto  30
   29:  iconst_0
   30:  invokevirtual #5; //Method java/io/PrintStream.println:(Z)V
   33:  getstatic #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   36:  iload_1
   37:  invokestatic  #6; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
   40:  iload_1
   41:  invokestatic  #6; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
   44:  if_acmpne 51
   47:  iconst_1
   48:  goto  52
   51:  iconst_0
   52:  invokevirtual #5; //Method java/io/PrintStream.println:(Z)V
   55:  return
}

(Incidentally, you can get this output by running javap -c JavaWTF.)

So basically, Integer.valueOf is being called to do the Integer boxing. From the 1.6 JavaDocs, I see:

public static Integer valueOf(int i)

Returns a Integer instance representing the specified int value. If a new Integer instance is not required, this method should generally be used in preference to the constructor Integer(int), as this method is likely to yield significantly better space and time performance by caching frequently requested values.

So sometimes it returns cached values, and sometimes it doesn't. If this functions returns an Integer via new Integer all the time, then all == comparisons will fail. However, if it returns the same object for some invocations, we'll get the observed behavior.

At this point, I was stuck - I didn't know where to go to look at some real Java 6 source code, but I bet the Apache Harmony guys knew a thing or two about all the quirks of the Java platform, so I took a peak at their Integer.java class:

public static Integer valueOf(int i) {
    if (i < -128 || i > 127) {
        return new Integer(i);
    }
    return valueOfCache.CACHE [i+128];
}

static class valueOfCache {
    /**
     * <p>
     * A cache of instances used by {@link Integer#valueOf(int)} and auto-boxing.
     */
    static final Integer[] CACHE = new Integer[256];
   
    static {
        for(int i=-128; i<=127; i++) {
            CACHE[i+128] = new Integer(i);
        }
    }
}

Ha! So I guess "most frequently used" integers means any integer between -128 and 127 (not integers your program has used before). No wonder!

Wednesday, December 21, 2011

Goodbye wmii. Hello i3!

A colleague recently recommend i3 to me, and I thought it was a rather good idea considering the problems I've been having with wmii (weirdly complicated configuration syntax, and problems with AWT).

wmii


(Notice the dialog box is not rendered correctly on the bottom right)

i3



The Swing problems are fixed in the HEAD of wmii's development branch, but I didn't notice that before I already committed to i3 (which is quite similar to wmii, but is less complicated to configure).

In the Debian/Ubuntu repositories, the latest version of i3 is 3.e (I think), but due to the configuration changes between 3 and 4, there may be some confusion about how to set up a status bar. The way to do it is to use i3status with the bar configuration directive with a 4.x+ release. You'll have to grab both i3wm and i3status from their respective repos and build the packages yourself. On Squeeze, apply this patch to i3 version 4.1 to make sure it builds correctly:

diff -rupN a/debian/control b/debian/control
--- a/debian/control    2011-11-11 14:40:38.000000000 -0800
+++ b/debian/control    2012-03-12 17:26:12.809273870 -0700
@@ -3,7 +3,7 @@ Section: utils
 Priority: extra
 Maintainer: Michael Stapelberg <michael@stapelberg.de>
 DM-Upload-Allowed: yes   
-Build-Depends: debhelper (>= 7.0.50~), libx11-dev, libxcb-util0-dev (>= 0.3.8), libxcb-ke
ysyms1-dev, libxcb-xinerama0-dev (>= 1.1), libxcb-randr0-dev, libxcb-icccm4-dev, libxcurso
r-dev, asciidoc (>= 8.4.4), xmlto, docbook-xml, pkg-config, libev-dev, flex, bison, libyaj
l-dev, texlive-latex-base, texlive-latex-recommended, texlive-latex-extra, libpcre3-dev, l
ibstartup-notification0-dev (>= 0.10)
+Build-Depends: debhelper (>= 7.0.50~), libx11-dev, libxcb-aux0-dev, libxcb-atom1-dev, lib
xcb-keysyms1-dev, libxcb-xinerama0-dev (>= 1.1), libxcb-randr0-dev, libxcb-icccm1-dev, lib
xcursor-dev, asciidoc (>= 8.4.4), xmlto, docbook-xml, pkg-config, libev-dev, flex, bison,
libyajl-dev, texlive-latex-base, texlive-latex-recommended, texlive-latex-extra, libpcre3-
dev, libstartup-notification0-dev (>= 0.10)
 Standards-Version: 3.9.2
 Homepage: http://i3wm.org/

You can apply this patch and build with:

cd i3-4.1
patch -p0 < /path/to/i3.patch
dpkg-buildpackage -uc -us

One other thing to note is that the i3status bar will not display correctly if there any errors; you also won't get any notification of errors if the font you specify is not correct (or missing).

Here is the result of switching to i3:


You can find my i3 configuration here.

Sunday, September 18, 2011

Ditz bash completion

I just had an "Oh, so that's how you do it" moment. The boss likes ditz for issue management; but for a while, I've been agonizing about how to do bash completion in ditz. The answer is you have to source this file: /var/lib/gems/1.8/gems/ditz-0.5/contrib/completion/ditz.bash. Oh, so that's how you do it!