Euler Project: Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

import Data.Char 

main :: IO()
main = print $ sum $ map snd $ filter fst resultData 

resultData :: [(Bool, Int)]
resultData = map (\x -> (compareDigit $ show x, x)) inputData 

compareDigit :: String -> Bool
compareDigit s = s == digitPowerSum s 

digitPowerSum :: String -> String
digitPowerSum n = show . sum $ map (\x -> digitToInt x ^5) n 

inputData :: [Int]
inputData = [2..6*9^5] 

*Main> main
443839

Numerical type 사이의 변환 방법

Numerical Type 사이의 전환에 대해서 정리해 보았다.
여기(영어)와 여기(일어)의 정리가 잘 되어 있다.

고졸 수학실력에 알맞게 내가 알고 있는 숫자 형태, 예를 들면 정수, 분수, 소수, 부동소수로 분류하여 각각의 type 변환을 그림으로 정리해 보았다.

undefined 대신에 $notImplemented 또는 ($todo "주절주절")

Haskell code를 만들어갈 때 함수의 type만 작성하고 본체는 undefined로 두는 경우가 자주 있다. 예를 들면,

someFunction :: a -> b
someFunction = undefined

함수 본체 작성을 잊은 경우, 프로그램 실행시에 불친절한 error가 출력된다. compile시에는 문제없이 넘어간다.

shAegis:Haskell shaegis$ ghc myUtil.hs
[1 of 1] Compiling Main             ( myUtil.hs, myUtil.o )
Linking myUtil ...
shaegis$ ./myUtil
myUtil: Prelude.undefined

Development.Placeholders를 이용하면 compile시에도 error를 잡아주며 undefined된 위치까지 알려준다.

{-# LANGUAGE TemplateHaskell #-}
import Development.Placeholders 

someFunction :: a -> b
someFunction = $notImplemented 

Or 

someFunction = $(todo "주말까지 작성.")

compile을 하면 다음과 같이 error를 잡아준다.

shAegis:Haskell shaegis$ ghc myUtil.hs
[1 of 1] Compiling Main             ( myUtil.hs, myUtil.o )
myUtil.hs:24:17: Warning: Unimplemented feature
Linking myUtil ... 

Or 

myUtil.hs:24:19: Warning: TODO: 주말까지 작성.

Euler Project: Problem 29

Consider all integer combinations of a^b for 2  a  5 and 2  b  5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2  a  100 and 2  b  100?

Prelude Data.List> length $ nub $ [a^b | a <- [2..100], b <- [2..100]]
9183

Euler Project: Problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

main :: IO()
main = print $ 1 + sumOf2ndTo1001Diag 

sumOf2ndTo1001Diag :: Int
sumOf2ndTo1001Diag = sum $ map sumCurrDiag inputData 

--초항: 예를 들어 3x3은, prev인 1x1 + (3-1).
iniNum :: (Int, Int) -> Int
iniNum (prev, curr) = prev * prev + (curr - 1) 

--3x3에서는 iniNum에서 (3-1)의 등차수열.
sumCurrDiag :: (Int, Int) -> Int
sumCurrDiag (prev, curr) = 2 * ( 2 * iniNum (prev, curr) + 3 * (curr - 1))
--sumCurrDiag (prev, curr) = iniNum (prev, curr) * 4 + (curr - 1) * 6 

inputData :: [(Int, Int)]
inputData = zip baseData (tail baseData) 

baseData :: [Int]
baseData = [1,3..1001] 

*Main> main
669171001

Euler Project: Problem 27

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula  n²  79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, 79 and 1601, is 126479.

Considering quadratics of the form:

n² + an + b, where |a|  1000 and |b|  1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

import Data.Numbers.Primes
import Data.List
import Data.Ord 

main :: IO()
main = print $ snd $ maximumBy (comparing fst) quadraticPair 

quadraticPair :: [(Int, Int)]
quadraticPair = [(quadraticLength a b, quadraticProduct a b) | a <- [(-1000)..1000], b <- [(-1000)..1000]] 

quadraticProduct :: Int -> Int -> Int
quadraticProduct a b = a*b 

quadraticLength :: Int -> Int -> Int
quadraticLength a b = length $ takeWhile (== True) $ map (isPrime . (\n -> n^2 + a*n +b)) [0..] 

*Main> main
-59231

Euler Project: Problem 26

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2	=	0.5
1/3	=	0.(3)
1/4	=	0.25
1/5	=	0.2
1/6	=	0.1(6)
1/7	=	0.(142857)
1/8	=	0.125
1/9	=	0.(1)
1/10	=	0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.

Find the value of d  1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.

오랜 동안 고민했다. 마땅한 알고리듬이 떠오르지 않았다. 일반적인 방법론이 전혀...

한참을 고민 끝에 결국 구글신님께 계시를 받기로 하고 검색을 하였다.

순환소수에 대한 '정리'가 있음을 알게 되었다.

여기 자료가 매우 유용하였다. 여기(Japanese).

요점만 정리하면 다음과 같다.

#1. 기약분수(k/n)가 무한순환소수일때, 소숫점 첫째자리부터 길이 r의 순환구간이 반복되는 것과, 10^r == 1 (mod n)이 성립하는 것은 동치이다.

#2. 기약분수가 순수한 순환소수일때 분모는 반드시 10과 서로소 이다. 반대로 분모가 10과 서로소인 기약분수를 소수로 나타내면 반드시 순수한 순환소수가 된다. (순수한 순환소수란, 0.121212...같은 것. 0.3121212는 순수하지 않은 순환소수를 지칭.)

2와 5를 제거하는 이유는, reLen 알고리듬상 reLen이 무한루프에 빠져들기 때문임.

import Data.Numbers.Primes
import Data.List
import qualified Data.Set as Set
import Data.Ord 

main :: IO()
main = print $ fst $ maximumBy (comparing snd) $ zip [1..1000] $ map reciprocalLength [1..1000] 

reciprocalLength :: Integer -> Integer
reciprocalLength n = reLen $ remove2or5 n 

remove2or5 :: Integer -> Integer
remove2or5 n = product $ Set.toList $ Set.difference (Set.fromList $ primeFactors n) (Set.fromList [2,5])
--remove2or5 n = product $ delete 5 $ delete 2 $ nub $ primeFactors n 

reLen :: Integer -> Integer
reLen n
    | n == 0 || n == 1  = 0
    | otherwise         = head [ r | r <- [1..], 10^r `mod` n == 1] 

*Main> main
983