Everyday word 2009-08-27

lavatory n.厕所, 盥洗室

amour n. 奸情,恋情

stork n. 鹳
ebb n.退潮; 落潮衰退; 衰落 vi.(指潮水)退; 落减少; 衰落
scavenger n.捡破烂的人食腐动物

slack adj.松(弛)的清淡的, 不活跃的懈怠的, 马虎的n.(绳索等)松弛部分宽松裤vt. & vi.懈怠; 偷懒减速; 放松

egress n. 外出 出路, 出口

wax n.蜡 vt.给…打蜡

carp n.鲤鱼vi.挑剔; 吹毛求疵; 找茬儿
codfish n.鳕鱼

Euler Project 112

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.
Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.
We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.
Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.
Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.
Find the least number for which the proportion of bouncy numbers is exactly 99%.

My Solution

(defun IsBouncyNumber(n)

  (let* ((numberstr (format nil "~a" n))

          (strlength (- (length numberstr) 2))

          (IsUp NIL)

          (IsDown NIL))

    (loop for i from 0 to strlength

           do(progn (if (> (char-int (elt numberstr i))

                                 (char-int (elt numberstr (+ i 1))))

                        (setq IsDown T)

                        (progn (if (< (char-int (elt numberstr i))

                                       (char-int (elt numberstr (+ i 1))))

                                  (setq IsUp T))))))

    (if (and IsDown IsUp)

        T

        NIL)))

(defun Euler112(n)

  (let ((constnum 99)

         (num 0)

         (currentnum 0))

    (loop for i from 100 to n

            do(progn (if (IsBouncyNumber i)

                              (progn (incf num)

                                        (setq currentnum i)))

                          (if (= 99 (/ (* num 100) i))

                              (return currentnum))))))

Books I want to read from Aug~Sep

Here is is a list of books I want to read in next two months

1. 
   《中国哲学史大纲》
   


2. 
   《A new kind of science》
   


3. 
   《文艺复兴简史》（原版）
   


4. 
   《当颜色的声音尝起来是甜的》
   


5. 
   《科学的算计》
   


6. 《集异璧》

Euler Project 39

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p  1000, is the number of solutions maximised?

My Solution

(defun Euler39(n)

  (let ((maxnum 0)

         (currentnum 0)

         (pNum 0))

    (loop for i from 10 to n

            for j=0

            do (progn (setq currentnum (loop for k from 1 to (floor (/ i 3))

                                                         when (integerp (/ (- (expt i 2) (* 2 k i))

                                                                                    (- (* 2 i) k)))

                                                         sum 1))

       (if (> currentnum maxnum)
            (progn (setq maxnum currentnum)

                                           (setq pNum i)))))

    pNum))

Everyday word 2009-08-25

coupon n.礼券, 优惠券订货单, 参赛表

ambient adj.周围的, 包围着的

expunge vt.擦掉, 除去, 删去, 消除
tacit adj.暗示的, 不言而喻的
repentant adj. 后悔的,悔改的,有悔改表现的
hallucinate vt.使产生幻觉
by no means n.绝不, 一点也不
impersonate vt.扮演模仿, 假冒
relent vi.怜悯; 变温和; 变宽厚
fervent adj.热诚的, 热烈的

Euler Project 58

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31

38 17 16 15 14 13 30

39 18  5  4  3 12 29

40 19  6  1  2 11 28

41 20  7  8  9 10 27

42 21 22 23 24 25 26

43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13  62%.
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

My Solution

(defun  primep (n)

        (cond ((minusp n) 'nil)

                  ((= 2 n) t)

                  ((evenp n) 'nil)

                  ((= 1 n) 'nil)

                  (t (let ((limit (floor (sqrt n))))

                      (do ((i 3 (incf i 2)))

                            ((> i limit) t)

                            (if (= 0 (mod n i)) (return-from primep 'nil)))))))

(defun Euler58(n)

  (let ((tempvar 0)

         (square 0)

         (spiralstep 0))

    (loop for i from 3 to n by 2

        do(progn (setq square (* i i))

                     (setq spiralstep (- i 1))

     (if (primep square)
         (incf tempvar))
     (if (primep (- square spiralstep))
         (incf tempvar))
     (if (primep (- square spiralstep spiralstep))
         (incf tempvar))
     (if (primep (- square spiralstep spiralstep spiralstep))
         (incf tempvar))
     (if (< (/ tempvar (- (* 2 i) 1.0))
             0.1)
         (return i))))))

Others' Solution

First Solution(I do not want to change the format, I will check the solution on the ProjectEuler)

(defun euler058 ()
(spiral-outwards 1000000000))
  

(defun spiral-outwards (bound)
(iterate loop ((number-of-diagonals 5)
(number-of-primes 3)
(side 3)
(dne 3)
(dsw 7)
(dnw 5)
(linear-term 8))
(if (< (/ number-of-primes number-of-diagonals) 1/10)
(cons side (/ number-of-primes number-of-diagonals))
(let ((new-dne (+ dne linear-term 2))
(new-dsw (+ dsw linear-term 6))
(new-dnw (+ dnw linear-term 4)))
(if (>= (max new-dne new-dsw new-dnw) bound)
(error "Too big for primeality test!")
(let ((new-primes (count-if #'(lambda (p) (prime-p p))
(list new-dne new-dsw new-dnw))))
(loop (+ number-of-diagonals 4)
(+ number-of-primes new-primes)
(+ side 2)
new-dne
new-dsw
new-dnw
(+ linear-term 8))))))))
  

(defun prime-p (n)
(unless (< n 25000000000)
(error "primality-by-millers-test: invalid for n >= 25000000000"))
(cond ((< n 2047)
(millers-test n 2))
((< n 1373653)
(and (millers-test n 2) (millers-test n 3)))
((< n 25326001)
(and (millers-test n 2) (millers-test n 3) (millers-test n 5)))
(:else
(and (/= n 3251031751) (millers-test n 2)
(millers-test n 3) (millers-test n 5) (millers-test n 7)))))
 

 (defun millers-test (n b)
(let ((n-1 (1- n)))
(multiple-value-bind (s m) (factor-out-2s n-1)
(let ((z (exp-mod b m n)))
(if (or (= z 1) (= z n-1))
t
(do ((j 1 (1+ j))
(z (exp-mod z 2 n) (exp-mod z 2 n)))
((>= j s) nil)
(if (= z n-1)
(return-from millers-test t))))))))

(defun factor-out-2s (n)
(iterate loop ((m n)
(s 0))
(multiple-value-bind (q r) (floor m 2)
(if (= r 1)
(values s m)
(loop q (1+ s))))))
 

 (defun exp-mod (base power modulus)
(iterate loop ((res 1)
(n power)
(a base))
(if (plusp n)
(loop (if (oddp n) (mod (* a res) modulus) res)
(ash n -1)
(mod (* a a) modulus))
res)))

Second Solution

(loop
for side = 0 then (if (= side 3) 0 (1+ side))
for size = 3 then (if (zerop side) (+ 2 size) size)
for no = 3 then (+ (1- size) no)
count (primep no) into primes
count no into total
until (and (zerop side) (<= (/ primes total) 1/10))
finally (return (- size 2)))

Congratulations to myself! Level2 for Project Euler

I think the road would be harder and harder in future. Anyway, I got the Level 2.

Euler Project 57

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.
In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

My Solution

(defun Euler57(n)

  (let ((num 0)

         (x (/ 1 2))

         (temp 0))

    (loop for i from 1 to n

         do(progn (setq temp (+ 1 x))

                      (if (> (length (format nil "~a" (numerator temp)))

                              (length (format nil "~a" (denominator temp))))

                          (progn (incf num) (setq x (/ 1 (+ 2 x))))

                          (setq x (/ 1 (+ 2 x))))))

    num))

A new kind of science

A mazing book, a new view, a wonderful software, a great author. So expensive and I cannot by one in China. Could someone give me one copy?

Everyday word 2009-08-24

scaffold n.脚手架断头台

collation n. 核对, 校勘; 考订, 对照 冷食小吃, 便餐
hunch n.预感, 直觉 vt.使…隆起
mutation n.变化; 转变; 突变; 变异变种; 突变体
napkin n.餐巾〈英·正〉 尿布
azure adj., n. 天蓝色(的)
velet n.丝绒, 天鹅绒
lounge n.休息厅, 休息室; 客厅vi.懒散地斜倚[靠坐]vt.懒洋洋地打发(时间) 
grumpy adj.脾气坏的, 生气的
acupunture n.针灸(疗法)

Get the w3wp process id fron Windows Server 2008

If you are doing the SharePoint Dev work, you must have to debug what you have done and you need attach the SharePoint process ID to your Visual Studio. When you do it on Windows Server 2003, you can just run the iisapp to get the process id. How about Windows Serve 2008? It does not work any more. We have another candidate .

%windir%\system32\inetsrv\appcmd.exe list wp

Euler Project 129

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.
Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.
The least value of n for which A(n) first exceeds ten is 17.
Find the least value of n for which A(n) first exceeds one-million.

My Solution

(defun A(n)

  (let ((reminder 1)

          (Ncount 1))

    (loop

      (progn (if (/= (gcd 10 n) 1)

                     (return Ncount))

                (if (/= 0 reminder)

                    (progn (setq reminder (rem (+ (* reminder 10)

                                                                    1)

                                                              n))

                               (incf Ncount))

                    (return Ncount))))

    Ncount))

(defun Euler129(n)

  (loop for i from 1000001 to n by 2

        do(progn (if (> (A i) 1000000)

                          (return i)))))

Euler Project 71

Consider the fraction, n/d, where n and d are positive integers. If nd and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d  8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d  1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

My Solution

(defun Euler71(n)

  (let ((constnumber (/ 3 7))

         (currentnumber 0)

         (tempar 0)

         (low 0)

         (high 0)

         (num 0))

    (loop for i from 100000 to n

        do(progn (setq high (ceiling (* i (/ 3 7))))

                      (setq low (- high 200))

                      (loop for j from low to high

  do(progn (setq tempar (/ j i))
                (if (and (= 1 (gcd i j))
                            (> tempar currentnumber)
                            (< tempar constnumber))
                    (progn (setq currentnumber tempar)
                              (incf num)))))))

    currentnumber))

Euler Project 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

My Solution

(defun  primep (n)

        (cond ((minusp n) 'nil)

                  ((= 2 n) t)

                  ((evenp n) 'nil)

                  ((= 1 n) 'nil)

                  (t (let ((limit (floor (sqrt n))))

                      (do ((i 3 (incf i 2)))

                            ((> i limit) t)

                            (if (= 0 (mod n i)) (return-from primep 'nil)))))))

(defun ConvetToNum(l)

  (let ((lengthoflist (length l))

         (num 0))

    (loop for i from 0 to (- lengthoflist 1)

           do(progn (setq num (+ num

                                          (* (elt l i)

                                              (expt 10 (- lengthoflist (+ i 1))))))))

    num))

(defun Euler41()

  (let ((alllist (p (list 1 2 3 4 5 6 7)))

         (currentprime 0)

         (tempvar 0))

    (loop for i from 0 to 5039

         do(progn (setq tempvar (ConvetToNum (elt alllist i)))

                      (if (primep tempvar)

                          (setq currentprime tempvar))))

    currentprime))

Euler Project 73

Consider the fraction, n/d, where n and d are positive integers. If nd and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d  8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d  10,000?

My Solution

(defun Euler73v2(n)

  (let ((thirdnum 0)

         (halfnum 0))

    (loop for i from 1 to n

          sum(progn (setq thirdnum (floor (/ i 3)))

                         (setq halfnum (ceiling (/ i 2)))

                         (loop for j from thirdnum to halfnum

                             when (and (= (gcd i j) 1)

                                            (> (/ j i) (/ 1 3))

                                            (< (/ j i) (/ 1 2)))

                             sum 1)))))

Euler Project 120

Let r be the remainder when (a1)ⁿ + (a+1)ⁿ is divided by a².

For example, if a = 7 and n = 3, then r = 42: 6³ + 8³ = 728  42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that r_max = 42.

For 3  a  1000, find  r_max.

My Solution

(defun MaxReminder(a)

  (loop for i from 1 to (* 2 a) by 2

          maximize (rem (* 2 a i) (* a a))))

(defun Euler120(n)

  (loop for i from 3 to n

          sum (MaxReminder i)))

Euler Project 69

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

n	Relatively Prime	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

It can be seen that n=6 produces a maximum n/φ(n) for n  10.

Find the value of n  1,000,000 for which n/φ(n) is a maximum.

My Solution

(defun  primep (n)

        (cond ((minusp n) 'nil)

                  ((= 2 n) t)

                  ((evenp n) 'nil)

                  ((= 1 n) 'nil)

                  (t (let ((limit (floor (sqrt n))))

                      (do ((i 3 (incf i 2)))

                            ((> i limit) t)

                            (if (= 0 (mod n i)) (return-from primep 'nil)))))))

(defun totient(n)

  (let ((primelist (loop for i from 1 to (floor (sqrt n))

                                when (and (zerop (rem n i))

                                                (primep i))

                                collect i

                                when (and (integerp (/ n i))

                                                (primep (/ n i))

                                                (null (eq (/ n i) i)))

                                collect (/ n i))))

    (* n (apply #'*

                    (mapcar #'(lambda(x)(/ (- x 1) x))

                                primelist)))))

(defun Euler69(n)

  (let ((maxn 0)

         (currentnum 0)

         (maxnum 0)) 

    (loop for i from 5 to n

            do(progn (setq currentnum (/ i (totient i)))

                          (if (> currentnum maxnum)

                              (progn (setq maxnum currentnum)

                                        (setq maxn i)))))

    maxn))

Everyday word 2009-08-22

totient n. 欧拉φ函数

dagger n.匕首; 短剑

cruelty n.残忍, 残酷残忍的行为, 尖刻的语言

axiom n.公理

pedestal n.底座, 基座

epic adj.史诗般的极大的, 宏大的n.叙事诗, 史诗惊人之举

hazardous adj. 冒险的, 有危险的

toad n.蟾蜍, 癞蛤蟆

monstrous adj.极可恶的; 令人震惊的尺寸大得不顺眼的, 大得古怪的

ginger n.姜, 生姜

小学时候的家长会

小学的时候，一点也不怕家长会。原因极其简单，我的老师都和我妈妈在同一个办公室，根本就不需要什么家长会了。

虽然家长会对我来说，可有可无，可我是十分期望家长会的，因为这是一个和同学玩的一个日子。

我所在的小学，都是晚上开家长会，因为是在乡下，白天家长们都要出去干活，做事，只有晚上才有时间。所以每到家长会的那个晚上，家长们就从十里八乡的赶过来，吵吵闹闹，十分的热闹。一般来说，我的小学到了晚上就十分的安静，除了住在学校的老师和家属，晚上基本是没有其他什么人的。晚上也没有什么晚自习，补课什么的。除非有的老师晚上要加班，改考卷，改作业什么的，晚上的教学楼总是黑漆漆的一片片。可是在这个特别的晚上，就变的灯火通明起来了。

每次开家长会的时候，班主任会叫班长，学习委会几个人提早一个小时来，帮着摆座椅，把期中的考卷，平时的作业考卷摆在同学的桌上，当家长们陆续到了，还有充当礼仪小姐的工作，把家长引导到其孩子的座位上。家长们都来了，孩子们在家中也不一定待的住，也纷纷的跟来。来了，自然不会跟到教室里面去，所以都聚在了操场上，一堆堆的，说说笑笑，吵吵闹闹，有的时候巡视的校长，政教主任不得不来制止我们过于喧闹的声响。

我这个时候，当然也是和自己平时要好的几个同学在一起。我现在还记得玩的一个游戏，一群的同学分成两队，玩一个我已经不知道该怎么说的游戏，就是电人，救人，摸一下基地，等级升高。。。其实平时也有玩，早上做完广播体操，有十分钟的时间，我们常常就留在操场上玩这种游戏，可是十分钟总是十分的短暂，常常是刚起个头，还没有尽兴，就上课了。而这个时候，可以玩一两个小时，常常玩的筋疲力尽才罢手。

家长会常常一两个小时之后就结束了，结束的时间根据年级不同而定，常常是高年级的比低年级的迟。就算结束了，老师周围还是围着许多的家长，对自己的孩子的学业提着各种问题。而我的同学也随着父母亲们纷纷离去，我这个时候，就到我妈妈的班级，或是到其它的班级上瞎逛，也不知道瞎逛什么，反正就是瞎逛，听听八卦，翻翻考卷，一个愉快的晚上就这样落下了帷幕。

Euler Project 95

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496  14288  15472  14536  14264 ( 12496  ...)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

My Solution

(defun factorialsum(n)

  (let* ((sqrtofn (sqrt n)) 

         (numbersum (loop for i from 2 to (floor sqrtofn)

                             when (zerop (rem n i))

                                      sum (+ i (/ n i)))))

         (progn (if (integerp sqrtofn)

                        (setq numbersum (- numbersum sqrtofn)))

   (+ numbersum 1))))

(defun lenghtofchain(n)

  (let ((original n)

(current n)

(lenght 1)

(previous 0))

    (loop 

      (progn (setq current (factorialsum current))

    (if (> current 1000000)

        (return 0))

    (if (= current original)

        (progn (return lenght))

        (if (= current 1)

            (progn (return lenght))

            (if (= current previous)

                (return 0)

                (if (> lenght 1000)

                     (return 0)))))

    (setq previous current)

    (incf lenght)))))

(defun Euler95(n)

  (let ((currentnumber 1)

         (maxlenght 0)

         (chainnumber 0)

         (currentlenght 0))

    (loop for i from 2 to n

         do(progn (setq currentlenght (lenghtofchain i))

                       (if (> currentlenght maxlenght)

                            (progn (setq maxlenght currentlenght)

                            (setq chainnumber i)))))

    chainnumber))