21. Amicable Numbers

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 \text{ and } 110\); therefore \(d(220) = 284\). The proper divisors of \(284\) are \(1, 2, 4, 71 \text{ and } 142\); so \(d(284) = 220\).

Evaluate the sum of all the amicable numbers under \(10,000\).

Solution in R
  • Create a function that returns TRUE if the number is amicable:
> amicable <- function(x){
+   
+   if (x==1){
+     return (FALSE)
+     }
+   
+   # sum of proper divisors of x
+   y <- sum(c(1:(x-1))[x%%c(1:(x-1))==0])
+  
+   # sum of proper divisors, using sum from above
+   z <- sum(c(1:(y-1))[y%%c(1:(y-1))==0])
+   
+   # True if amicable. Z = NA if x is prime.
+   (x == z) & (x !=y) & !is.na(z) 
+   
+ }
  • Examples:
> amicable(220)
> amicable(284)
> amicable(5)
[1] TRUE
[1] TRUE
[1] FALSE
  • Loop through for solution.
> w <- 0
> for (i in 1:9999){
+   
+   if (amicable(i)==TRUE){
+     w = w+i
+   }
+ }
> 
> w
[1] 31626
Solution in Python
  • Function:
> import numpy as np
+ 
+ def amicable(x):
+     y = sum(np.arange(1,x)[x % np.arange(1,x) == 0])
+     z = sum(np.arange(1,y)[y % np.arange(1,y) == 0])
+     return (x == z) & (x !=y)
  • Test:
> print(" 220:" , amicable(220), "\n" ,
+       "284:", amicable(284), "\n",
+       "5:", amicable(5))
 220: True 
 284: True 
 5: False
  • Loop:
> w = 0 
+ for i in range(1,10000):
+     if amicable(i) == True:
+         w+=i
+ 
+ w
31626

22. Names Scores

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

Solution in R
  • Read in file and format:
> # Read in text lines
> x <- readLines("p022_names.txt",warn=FALSE)
> # Separate names by comma and remove from list format
> x <- unlist(strsplit(x,","))
> 
> # Remove everything that's not A to Z.
> library(stringr)
> x <- str_replace_all(x,"[^A-Z]","")
> 
> # Sort Ascending
> x <- sort(x)
> 
> head(x)
[1] "AARON" "ABBEY" "ABBIE" "ABBY"  "ABDUL" "ABE"
  • Create lookup for letter number:
> # Create data frame of letters. Use LETTERS from base R
> LetterNum <- data.frame(row.names = LETTERS,
+                         LetNum = 1:26)
> 
> head(LetterNum)
  LetNum
A      1
B      2
C      3
D      4
E      5
F      6
  • Loop through all words and calculate and sum the NameScore:
> w = 0
> for (i in x) {
+   
+   # Calculate the sum of all the letters
+   z <- sum(LetterNum[unlist(strsplit(i,"")),"LetNum"])
+   
+   # NameScore = sum of letters times index number
+   NameScore <- z * which(x == i)
+   w = w + NameScore
+   
+ }
> 
> w
[1] 871198282
Solution in Python
> # open and separate by comma
> 
> with open('p022_names.txt') as f:
>     names = f.read().split(',')
>     names.sort()
> names[0:5]
+ 
+ # Will need to strip the extra quotes
['"AARON"', '"ABBEY"', '"ABBIE"', '"ABBY"', '"ABDUL"']
> names[0].strip('"')
'AARON'
> names = [name.strip('"') for name in names]
+ names[0:5]
['AARON', 'ABBEY', 'ABBIE', 'ABBY', 'ABDUL']
> # ascii_uppercase is similar to LETTERS in base R
+ 
+ from string import ascii_uppercase
+ def SumLetters(word):
+     return sum(ascii_uppercase.index(x)+1 for x in word)
+     
+ SumLetters(names[0])
49
> print (sum(i*SumLetters(x) for i,x in enumerate(names,start=1)))
871198282

23. Non-abundant Sums

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of \(28\) would be \(1 + 2 + 4 + 7 + 14 = 28\), which means that \(28\) is a perfect number.

A number \(n\) is called deficient if the sum of its proper divisors is less than \(n\) and it is called abundant if this sum exceeds \(n\).

As \(12\) is the smallest abundant number, \(1 + 2 + 3 + 4 + 6 = 16\), the smallest number that can be written as the sum of two abundant numbers is \(24\). By mathematical analysis, it can be shown that all integers greater than \(28123\) can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Solution in R
> library(numbers)
> 
> # TRUE if abundant
> abundant <- function(x){
+   sum(divisors(x)[1:length(divisors(x))-1])>x
+ }
> 
> # Create Vector of abundant numbers
> AbundList <- c(12)
> 
> for (i in 13:(28123-12)){
+   
+   if (abundant(i)==TRUE){
+     
+     AbundList <- c(AbundList,i)
+     
+   }
+ }
> 
> # Maximum
> max(AbundList)
[1] 28110
> # Create grid of all combinations
> AbundGrid <- expand.grid(x=AbundList, y=AbundList)
> 
> AbundGrid$z = AbundGrid$x + AbundGrid$y
> 
> AbundGrid[1:5,]
   x  y  z
1 12 12 24
2 18 12 30
3 20 12 32
4 24 12 36
5 30 12 42
> # All unique sums of 2 abundant numbers
> AbundUnique <- unique(AbundGrid$z)
> AbundUnique[1:10]
 [1] 24 30 32 36 42 48 52 54 60 66
> max(AbundUnique[AbundUnique<28124])
[1] 28123
> a <- sum(c(1:28123))
> b <- sum(AbundUnique[AbundUnique<28124])
> 
> # Sum of numbers through 28,123 
> # minus sum of abundant numbers through 28,123
> 
> a-b
[1] 4179871

24. Lexicographic permutations

A permutation is an ordered arrangement of objects. For example, \(3124\) is one possible permutation of the digits \(1, 2, 3 \text{ and } 4\). If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of \(0, 1 \text{ and } 2\) are:

\[012 \quad 021 \quad 102 \quad 120 \quad 201 \quad 210\]

What is the millionth lexicographic permutation of the digits \(0, 1, 2, 3, 4, 5, 6, 7, 8 \text{ and } 9\)?

Solution in R
> library(gtools)
> 
> # permutations function creates a matrix
> # in order of smallest to greatest
> permutations(3, 3, c(0:2))
     [,1] [,2] [,3]
[1,]    0    1    2
[2,]    0    2    1
[3,]    1    0    2
[4,]    1    2    0
[5,]    2    0    1
[6,]    2    1    0
> x <- permutations(10, 10, c(0:9))
> 
> # Row 1,000,000
> paste0(x[1000000,], collapse = "")
[1] "2783915460"
Solution in Python
> from itertools import permutations  
+   
+ # Get all permutations of [0, 1, 2]  
+ perm = permutations([0, 1, 2])  
+   
+ # Print the obtained permutations  
+ for i in list(perm):  
+     print (i)  
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
> a = list(permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))[999999]
+ 
+ a = map(str, a)    
+ a = ''.join(a)  
+ int(a)
2783915460

25. 1000-digit Fibonacci Number

The Fibonacci sequence is defined by the recurrence relation:

\(Fn = Fn−1 + Fn−2\), where \(F1 = 1\) and \(F2 = 1\). Hence the first \(12\) terms will be:

\(F1 = 1\)
\(F2 = 1\)
\(F3 = 2\)
\(F4 = 3\)
\(F5 = 5\)
\(F6 = 8\)
\(F7 = 13\)
\(F8 = 21\)
\(F9 = 34\)
\(F10 = 55\)
\(F11 = 89\)
\(F12 = 144\)

The \(12^{th}\) term, \(F12\), is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain \(1000\) digits?

Solution in R
> library(gmp) 
> 
> # fibnum(number in sequence) 
> # 50th fibonacci number
> fibnum(50)
Big Integer ('bigz') :
[1] 12586269025
> # Loop through
> x <- 1
> 
> while (nchar(as.character(fibnum(x))) < 1000) {
+   x <- x + 1
+ }
> 
> #answer 
> x
[1] 4782
> fibnum(x)
Big Integer ('bigz') :
[1] 1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816
Solution in Python
> a = 1
+ b = 1
+ n = 2
+ 
+ while len(str(b)) < 1000:
+     b = a+b
+     a = b-a
+     n = n + 1
+ print (n)
4782
> str(b)
'1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816'