Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142 so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

(defun divisor-p (num divisor)
  "Tests if divisor is a divisor of num"
  (zerop (mod num divisor)))

(defun divisors (num)
  "Returns a list of num's divisors"
  (do ((i 2 (1+ i))
         (result '(1)))
      ((> i (isqrt num)) (remove-duplicates result))
    (when (divisor-p num i)
      (setf result (append result (list i (/ num i)))))))

(defun sum-divisors (num)
  "Sums the divisors of num"
  (reduce #'+ (divisors num)))

(defun amicable-p (num)
  "Tests if num is amicable"
  (let ((divisors-sum (sum-divisors num)))
    (when (and (= num (sum-divisors divisors-sum)) 
                       (not (= num divisors-sum)))
      num)))

(defun amicable-sum (limit)
  "Returns the sum of all amicable numbers below limit"
  (do ((i 1 (1+ i))
         (result 0))
      ((>= i limit) result)
    (when (amicable-p i)
      (incf result i))))
  
(defun euler-21 ()
  (amicable-sum 10000))

n! means n × (n − 1) × ... × 3 × 2 × 1

Find the sum of the digits in the number 100!

(defun add-digits (num)
  "Returns the sum of the number's digits"
  (let ((sum 0)
         (num-string (write-to-string num)))
     (dotimes (i (length num-string))
       (setf sum (+ sum (digit-char-p (schar num-string i)))))
    sum))

(defun fact (num)
  (if (= num 1)
      1
      (* num (fact (1- num)))))

(defun euler-20 ()
  (add-digits (fact 100)))

You are given the following information, but you may prefer to do some research for yourself.

* 1 Jan 1900 was a Monday.
* Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
* A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

(defconstant +months+ '("Jan" "Feb" "Mar" "April" "May" "June"
   "July" "Aug" "Sept" "Oct" "Nov" "Dec"))

(defconstant +days+ '("Sun" "Mon" "Tue" "Wed" "Thurs" "Fri" "Sat"))

(defun days-in-month (month year)
  "Returns the number of days in the month given the month and year"
  (cond ((member month '("Sept" "April" "June" "Nov") :test #'string=)
             30)
            ((and (string= "Feb" month) (zerop (mod year 4))) 29)
            ((string= "Feb" month) 28)
            (t 31)))

(defun move-ahead (today days)
  "Moves ahead a number of days and returns the day.
Example: (move-ahead 'Mon' 3) => 'Thurs'
         (move-ahead 'Sun' 8) => 'Mon'"
  (let ((cur-day-num (position today +days+ :test #'string=)))
    (elt +days+ (mod (+ cur-day-num days) 7))))

(defun euler-19 ()
  (let ((today "Mon")
         (result 0))
    (loop for year from 1900 to 2000 do
       (dolist (month +months+)
          (when (and (string= today "Sun") (> year 1900))
              (incf result))
          (setf today (move-ahead today (days-in-month month year)))))
       result))

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 5
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows it cannot be solved by brute force, and requires a clever method! ;o)

This problem is best solved by starting at the base and working up. Increment the number above each pair of nodes by the largest of the two nodes, and continue until you reach the top.

(defconstant +triangle+ 
  '(
    (75)
    (95 64)
    (17 47 82)
    (18 35 87 10)
    (20 04 82 47 65)
    (19 01 23 75 03 34)
    (88 02 77 73 07 63 67)
    (99 65 04 28 06 16 70 92)
    (41 41 26 56 83 40 80 70 33)
    (41 48 72 33 47 32 37 16 94 29)
    (53 71 44 65 25 43 91 52 97 51 14)
    (70 11 33 28 77 73 17 78 39 68 17 57)
    (91 71 52 38 17 14 91 43 58 50 27 29 48)
    (63 66 04 68 89 53 67 30 73 16 69 87 40 31)
    (04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)))

(defun bottom-two-rows (triangle)
  "Returns the bottom two rows of a triangle"
  (list (car (last (butlast triangle)))
         (car (last triangle))))

(defun first-node-and-stems (triangle)
  "Given two rows of a triangle, returns the first node and the
first node's stems.
Example: (first-node-and-stems '((2 4 6) (8 5 9 3))) => 2 8 5"
  (let ((node (caar triangle))
          (left-stem (first (cadr triangle)))
          (right-stem (second (cadr triangle))))
    (values node left-stem right-stem)))

(defun max-node (node left-stem right-stem)
  (max (+ node left-stem)
           (+ node right-stem)))

(defun sum-stems (rows)
  "Given two adjacent rows of a triangle, returns a list of the
maximum total of the stems for each node.
Example: (sum-stems '((2 4 6) (8 5 9 3))) => (10 13 15)"
  (when (first rows)
    (multiple-value-bind (node left-stem right-stem)
        (first-node-and-stems rows)
      (cons (max-node node left-stem right-stem)
                (sum-stems (mapcar #'cdr rows))))))

(defun max-route (triangle)
  "Returns the sum of the route that produces the maximum total of
the given triangle"
  (if (= (length triangle) 2)
      (multiple-value-bind (node left-stem right-stem)
           (first-node-and-stems triangle)
        (max-node node left-stem right-stem))
      (max-route (append (butlast (butlast triangle))
                                      (list (sum-stems
                                             (bottom-two-rows triangle)))))))

(defun euler-18 ()
  (max-route +triangle+))

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

(defun remove-hyphens (str)
  "Removes any hyphens from str"
  (remove #\- str))

(defun remove-spaces (str)
  "Removes any spaces from str"
  (remove #\Space str))

(defun euler-17 ()
  (+ (loop for i from 1 to 1000 sum
         (length (remove-hyphens (remove-spaces 
                                                       (format nil "~R" i)))))
     ;; SBCL does not include the word 'and', so add 
     ;; those letters also
     (* 3 99 9)))

2^(15) = 32768 and the sum of its digits is
3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^(1000)?

(defun add-digits (num)
  "Returns the sum of the number's digits"
  (let ((sum 0)
          (num-string (write-to-string num)))
    (dotimes (i (length num-string))
      (setf sum (+ sum (digit-char-p (schar num-string i)))))
    sum))

(defun euler-16 ()
  (add-digits (expt 2 1000)))

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20×20 grid?

Since we can not backtrack, we can only move down and right. If we have a 2x2 grid, this means every route consists of exactly 2 right moves and 2 down moves. We can think of the routes as a set of moves, such as (d d r r), and the total number of routes will be all the different combinations of the set minus the identical combinations. To find the number of unique combinations, suppose we have the route (d d r r). Treating each move distinctly, lets write the set as (d1 d2 r1 r2). Notice how this route is equal to the route(d2 d1 r2 r1), and we only want to count this as one route. It turns out that the number of unique routes per combination is 2!*2! = 4: (d1 d2 r1 r2) (d1 d2 r2 r1) (d2 d1 r1 r2)(d2 d1 r2 r1). This means each route in the set of all possible route combinations, 4!, will have 3 other identical routes in the set, resulting in 4!/(2!2!) unique routes. This formula applies to larger grids as well.

(defun factorial (n &optional (acc 1))
  (if (<= n 1)
      acc
      (factorial (- n 1) (* acc n))))

(defun grid-routes (x-dim y-dim)
  "Calculates the number of routes from the top left corner
of a grid to the bottom right corner, without backtracking"
  (let ((total-number-of-moves (+ x-dim y-dim)))
    (/ (factorial total-number-of-moves)
       (* (factorial x-dim)
           (factorial y-dim)))))

(defun euler-15 ()
  (grid-routes 20 20))

The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

I listed two solutions to this problem in Common Lisp below. alt-euler-14 strictly follows the formula and computes the solution inefficiently. euler-14 stores computed values in a hash table so it never applies the formula to the same number more than once.

;;; *collatz-table* holds the number of terms for previously performed
;;; collatz calculations.  For example, say that we already found
;;; the number of terms to compute 10, which is 7.  If we compute
;;; the number of terms for 13, as in the example above, when it
;;; reaches 10 it will find this value in the table and add 7 to
;;; the current terms value to get the answer.
(defparameter *collatz-table* (make-hash-table))

(defun collatz (num)
  (cond ((= num 1) 1)
            ((gethash num *collatz-table*)
             (gethash num *collatz-table*))
            ((evenp num)
              (setf (gethash num *collatz-table*)
                      (1+ (collatz (/ num 2)))))
             (t (setf (gethash num *collatz-table*)
                         (1+ (collatz (1+ (* 3 num))))))))

(defun euler-14 ()
  (let ((answer 0)
          (max-terms 0))
    (do ((x 1 (1+ x)))
          ((>= x 1000000) answer)
      (let ((terms-of-x (collatz x)))
         (when (> terms-of-x max-terms)
           (setf max-terms terms-of-x
                   answer x))))))

(defun alt-collatz (num &optional (term 1))
  (cond ((= num 1) term)
            ((evenp num) (alt-collatz (/ num 2) (1+ term)))
            (t (alt-collatz (1+ (* 3 num)) (1+ term)))))

(defun alt-euler-14 ()
  (let ((answer 0)
         (max-terms 0))
    (do ((x 1 (1+ x)))
          ((>= x 1000000) answer)
      (let ((terms-of-x (alt-collatz x)))
        (when (> terms-of-x max-terms)
             (setf max-terms terms-of-x
                     answer x))))))

Alt-euler-14 took 8.5 seconds. euler-14's first run took 3 seconds, but the second run took 0.28 seconds. This speed came at a cost of more memory.

I'm currenlty working on a spring application that uses Spring Security to manage logins and page access on my site. After following the general process to set up Spring Security, as outlined in many online tutorials, you can retrieve the user information stored in the session as follows:

final SecurityContext sc = SecurityContextHolder.getContext();
final Authentication auth = sc.getAuthentication();
auth.getPrincipal();

In a typical security setup auth.getPrincipal will return a Spring Security user object which contains the current user's login name, password and roles. For my application, I wanted this object to also contain the user's unique id. This can be accomplished by extending two classes in a typical spring security setup.

In Spring Security, the authenticationDao is responsible for looking up the user's credentials. In my application the users are stored in a database, so at first I used JdbcDaoImpl for this. I wanted to return the user id as well, so this class needed some slight modifications. My new class extended JdbcDaoImpl and looks similar to this:

public class JdbcDaoUserIdImpl extends JdbcDaoImpl {

    /**
     * Injected by spring
     */
    private UserDao userDao;

    public void setUserDao(UserDao userDao) {
        this.userDao = userDao;
    }

    /**
     * Returns a UserDetails object that also contains the user's unique id
     * 
     * @see org.springframework.security.userdetails.jdbc.JdbcDaoImpl#createUserDetails(java.lang.String,
     *      org.springframework.security.userdetails.UserDetails,
     *      org.springframework.security.GrantedAuthority[])
     */
    protected UserDetails createUserDetails(String username,
            UserDetails userFromUserQuery,
            GrantedAuthority[] combinedAuthorities) {
        String returnUsername = userFromUserQuery.getUsername();

        if (!isUsernameBasedPrimaryKey()) {
            returnUsername = username;
        }

        User user = userDao.getUser(username);

        return new UserId(user.getId(), returnUsername, userFromUserQuery
                .getPassword(), userFromUserQuery.isEnabled(), true, true,
                true, combinedAuthorities);
    }

}

Notice that instead of returning a Spring Security User object it returns a UserId object. This class extends the User class and simply has one additional field containing, as you guessed, the user Id. It looks something like this:

public class UserId extends User {
    
    private static final long serialVersionUID = -8275492272371421013L;
    private long id;

    public UserId( long id, String username, String password, boolean enabled,
            boolean accountNonExpired, boolean credentialsNonExpired,
            boolean accountNonLocked, GrantedAuthority[] authorities)
            throws IllegalArgumentException {
        super(username, password, enabled, accountNonExpired, credentialsNonExpired,
                accountNonLocked, authorities);
        this.id = id;
    }
    
    /** 
     * Sets the user's unique id in the server's session object
     * @param id the user's id
     */
    public void setId(long id) {
        this.id = id;
    }

    /** 
     * 
     * @return the user's unique id
     */
    public long getId() {
        return this.id;
    }
    
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append(super.toString()).append(": ");
        sb.append("Id: ").append(this.id).append("; ");
        return sb.toString();
    }
    

}

After updating the security configuration files to use the new classes , we can store as many details as we like in each session. To get to the details, in your servlets cast the auth.getPrincipal object to your new class, in our case UserId.

Abstract: When in System > Preferences > Screen Resolution, if you change the refresh rate and you monitor goes blank, reboot into the terminal, then from your home directory remove the file .config/monitors.xml

This week I was playing around with different desktop wallpapers for Ubuntu and wandered off into the screen resolution settings for gnome. Now, it has been a while since I configured my current monitor, so when I saw I had options for a faster refresh rate I just had to modify it, even though I should have known my monitor didn't support higher rates. I increased the refresh rate and my monitor immediately went blank, then displayed the message "Mode not supported". I patiently waited a couple minutes to see if Ubuntu would automatically revert the settings, but nothing happened. I rebooted the system.

I figured I would have to manually edit the xorg.conf file, something I've done before and have no problem doing. But to my surprise the login splash screen displayed. I logged in and the screen went blank with the same message blinking.

Evidently it must be some gnome user configuration rather than an xorg.conf problem since it happens only after logging in. From another computer I googled for answers, but none seemed to address my particular problem; most dealt with xorg configurations. Then I found a post stating gnome stores settings files in a series of .gnome directories, and removing these files would change my desktop setting back to default.

After booting into a terminal, I searched the files in those directories but none seemed to deal with monitor configurations. Desperate, I deleted them all. I went to log in again but the screen turned blank once again.

To solve this problem, I knew I had to find the configuration file that gnome modifies when configuring the monitor. I created a new user and logged in and opened Monitor Resolutions window. I changed the resolution this time, and saved the settings.

To find files that were recently modified, from your home directory type the command ls -atu | less, which list all files and directories and sorts by time last modified. If you were following my steps, you should notice that the .config directory was modified. Issuing the command again in that directory reveals that a file called monitors.xml was recently modified. Here lies the problem.

The monitors.xml file contains the monitor settings for each user, including screen refresh rate. I simply deleted this file, and everything returned to normal. All this hassle could have easily been resolved if the monitor settings revert back to the previous settings if the user doesn't confirm the changes within a few seconds time. Despite all the trouble, Ubuntu is still my favorite operating system.