From 7e7b56db42ceb8d2b8973eae678fa4b58d5d3659 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Wed, 13 May 2009 23:32:40 -0500 Subject: add old solutions --- 1.lua | 6 ++++ 1.pl | 5 +++ 10.lua | 21 ++++++++++++ 12.lua | 31 +++++++++++++++++ 13.lua | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 14.lua | 20 +++++++++++ 145.lua | 12 +++++++ 15.lua | 13 ++++++++ 17.lua | 38 +++++++++++++++++++++ 189.lua | 27 +++++++++++++++ 2.lua | 30 +++++++++++++++++ 2.pl | 18 ++++++++++ 21.lua | 24 ++++++++++++++ 3.lua | 8 +++++ 3.pl | 16 +++++++++ 3.sh | 1 + 4.lua | 16 +++++++++ 5.lua | 21 ++++++++++++ 6.lua | 13 ++++++++ 7.lua | 19 +++++++++++ 8.lua | 16 +++++++++ 21 files changed, 471 insertions(+) create mode 100644 1.lua create mode 100755 1.pl create mode 100644 10.lua create mode 100644 12.lua create mode 100644 13.lua create mode 100644 14.lua create mode 100644 145.lua create mode 100644 15.lua create mode 100644 17.lua create mode 100644 189.lua create mode 100644 2.lua create mode 100755 2.pl create mode 100644 21.lua create mode 100644 3.lua create mode 100755 3.pl create mode 100755 3.sh create mode 100644 4.lua create mode 100644 5.lua create mode 100644 6.lua create mode 100644 7.lua create mode 100644 8.lua diff --git a/1.lua b/1.lua new file mode 100644 index 0000000..fe66121 --- /dev/null +++ b/1.lua @@ -0,0 +1,6 @@ +#!/usr/bin/lua +local t = 0 +for i = 1, 999 do + if i % 3 == 0 or i % 5 == 0 then t = t + i end +end +print(t) diff --git a/1.pl b/1.pl new file mode 100755 index 0000000..85a8faa --- /dev/null +++ b/1.pl @@ -0,0 +1,5 @@ +#!/usr/bin/perl +use warnings; + +$t+=(!($_%5&& $_%3)?$_:0)for(1..999); +print "$t\n"; diff --git a/10.lua b/10.lua new file mode 100644 index 0000000..cca16c1 --- /dev/null +++ b/10.lua @@ -0,0 +1,21 @@ +function isprime(n) + if n < 2 then return false end + if n == 2 then return true end + if math.fmod(n, 2) == 0 then return false end + for i = 3, math.ceil(math.sqrt(n)), 2 do + if math.fmod(n, i) == 0 then return false end + end + return true +end + +local i = 3 +local sum = 2 +while true do + if i >= 1000000 then break end + if isprime(i) then + if sum + i < sum then print("overflow") end + sum = sum + i + end + i = i + 2 +end +print(sum) diff --git a/12.lua b/12.lua new file mode 100644 index 0000000..7ef1c0d --- /dev/null +++ b/12.lua @@ -0,0 +1,31 @@ +-- only valid when n > 1 +function num_factors(n) + local ret = 2 + local test = 2 + local limit = math.sqrt(n) + while test < limit do + if n % test == 0 then + ret = ret + 2 + end + test = test + 1 + end + if limit == math.floor(limit) then ret = ret + 1 end + return ret +end + +generate_triangle = coroutine.wrap(function() + local num = 0 + local add = 1 + while true do + num = num + add + add = add + 1 + coroutine.yield(num) + end +end) + +while true do + local n = generate_triangle() + local nn = num_factors(n) + print(n .. ": " .. nn) + if nn > 500 then break end +end diff --git a/13.lua b/13.lua new file mode 100644 index 0000000..bcef1dd --- /dev/null +++ b/13.lua @@ -0,0 +1,116 @@ +local nums = { + "37107287533902102798797998220837590246510135740250", + "46376937677490009712648124896970078050417018260538", + "74324986199524741059474233309513058123726617309629", + "91942213363574161572522430563301811072406154908250", + "23067588207539346171171980310421047513778063246676", + "89261670696623633820136378418383684178734361726757", + "28112879812849979408065481931592621691275889832738", + "44274228917432520321923589422876796487670272189318", + "47451445736001306439091167216856844588711603153276", + "70386486105843025439939619828917593665686757934951", + "62176457141856560629502157223196586755079324193331", + "64906352462741904929101432445813822663347944758178", + "92575867718337217661963751590579239728245598838407", + "58203565325359399008402633568948830189458628227828", + "80181199384826282014278194139940567587151170094390", + "35398664372827112653829987240784473053190104293586", + "86515506006295864861532075273371959191420517255829", + "71693888707715466499115593487603532921714970056938", + "54370070576826684624621495650076471787294438377604", + "53282654108756828443191190634694037855217779295145", + "36123272525000296071075082563815656710885258350721", + "45876576172410976447339110607218265236877223636045", + "17423706905851860660448207621209813287860733969412", + "81142660418086830619328460811191061556940512689692", + "51934325451728388641918047049293215058642563049483", + "62467221648435076201727918039944693004732956340691", + "15732444386908125794514089057706229429197107928209", + "55037687525678773091862540744969844508330393682126", + "18336384825330154686196124348767681297534375946515", + "80386287592878490201521685554828717201219257766954", + "78182833757993103614740356856449095527097864797581", + "16726320100436897842553539920931837441497806860984", + "48403098129077791799088218795327364475675590848030", + "87086987551392711854517078544161852424320693150332", + "59959406895756536782107074926966537676326235447210", + "69793950679652694742597709739166693763042633987085", + "41052684708299085211399427365734116182760315001271", + "65378607361501080857009149939512557028198746004375", + "35829035317434717326932123578154982629742552737307", + "94953759765105305946966067683156574377167401875275", + "88902802571733229619176668713819931811048770190271", + "25267680276078003013678680992525463401061632866526", + "36270218540497705585629946580636237993140746255962", + "24074486908231174977792365466257246923322810917141", + "91430288197103288597806669760892938638285025333403", + "34413065578016127815921815005561868836468420090470", + "23053081172816430487623791969842487255036638784583", + "11487696932154902810424020138335124462181441773470", + "63783299490636259666498587618221225225512486764533", + "67720186971698544312419572409913959008952310058822", + "95548255300263520781532296796249481641953868218774", + "76085327132285723110424803456124867697064507995236", + "37774242535411291684276865538926205024910326572967", + "23701913275725675285653248258265463092207058596522", + "29798860272258331913126375147341994889534765745501", + "18495701454879288984856827726077713721403798879715", + "38298203783031473527721580348144513491373226651381", + "34829543829199918180278916522431027392251122869539", + "40957953066405232632538044100059654939159879593635", + "29746152185502371307642255121183693803580388584903", + "41698116222072977186158236678424689157993532961922", + "62467957194401269043877107275048102390895523597457", + "23189706772547915061505504953922979530901129967519", + "86188088225875314529584099251203829009407770775672", + "11306739708304724483816533873502340845647058077308", + "82959174767140363198008187129011875491310547126581", + "97623331044818386269515456334926366572897563400500", + "42846280183517070527831839425882145521227251250327", + "55121603546981200581762165212827652751691296897789", + "32238195734329339946437501907836945765883352399886", + "75506164965184775180738168837861091527357929701337", + "62177842752192623401942399639168044983993173312731", + "32924185707147349566916674687634660915035914677504", + "99518671430235219628894890102423325116913619626622", + "73267460800591547471830798392868535206946944540724", + "76841822524674417161514036427982273348055556214818", + "97142617910342598647204516893989422179826088076852", + "87783646182799346313767754307809363333018982642090", + "10848802521674670883215120185883543223812876952786", + "71329612474782464538636993009049310363619763878039", + "62184073572399794223406235393808339651327408011116", + "66627891981488087797941876876144230030984490851411", + "60661826293682836764744779239180335110989069790714", + "85786944089552990653640447425576083659976645795096", + "66024396409905389607120198219976047599490197230297", + "64913982680032973156037120041377903785566085089252", + "16730939319872750275468906903707539413042652315011", + "94809377245048795150954100921645863754710598436791", + "78639167021187492431995700641917969777599028300699", + "15368713711936614952811305876380278410754449733078", + "40789923115535562561142322423255033685442488917353", + "44889911501440648020369068063960672322193204149535", + "41503128880339536053299340368006977710650566631954", + "81234880673210146739058568557934581403627822703280", + "82616570773948327592232845941706525094512325230608", + "22918802058777319719839450180888072429661980811197", + "77158542502016545090413245809786882778948721859617", + "72107838435069186155435662884062257473692284509516", + "20849603980134001723930671666823555245252804609722", + "53503534226472524250874054075591789781264330331690", +} + +local sum1 = 0 +for _, v in ipairs(nums) do + v = v:sub(1, 8) + sum1 = sum1 + tonumber(v) +end +local sum2 = 0 +for _, v in ipairs(nums) do + v = v:sub(9, 16) + sum2 = sum2 + tonumber(v) +end +sum2 = tostring(sum2) +sum2 = sum2:sub(1, sum2:len() - 8) +print(sum1 + tonumber(sum2)) diff --git a/14.lua b/14.lua new file mode 100644 index 0000000..96498ec --- /dev/null +++ b/14.lua @@ -0,0 +1,20 @@ +function collatz(n) + local sum = 1 + while true do + if n == 1 then break end + if n % 2 == 0 then n = n / 2 + else n = n * 3 + 1 end + sum = sum + 1 + end + return sum +end + +local max = 0 +local maxnum = 0 +for i = 1, 999999 do + local sum = collatz(i) + print(i .. ": " .. sum) + if sum > max then max = sum; maxnum = i end +end +print("--------") +print(maxnum .. ": " .. max) diff --git a/145.lua b/145.lua new file mode 100644 index 0000000..1713881 --- /dev/null +++ b/145.lua @@ -0,0 +1,12 @@ +-- this will take ~6h to run... need efficiency! +function reversible(n) + local revn = n:reverse() + local str = tostring(n + revn) + return not str:match("[02468]") +end + +local sum = 0 +for i = 1, 999999999 do + if i % 10 ~= 0 and reversible(tostring(i)) then sum = sum + 1 end +end +print(sum) diff --git a/15.lua b/15.lua new file mode 100644 index 0000000..8450302 --- /dev/null +++ b/15.lua @@ -0,0 +1,13 @@ +function combinations(n, r) + local numerator = 1 + local denominator = 1 + for i = n, n - r + 1, -1 do + numerator = numerator * i + end + for i = r, 1, -1 do + denominator = denominator * i + end + return numerator / denominator +end + +print(combinations(40, 20)) diff --git a/17.lua b/17.lua new file mode 100644 index 0000000..d745419 --- /dev/null +++ b/17.lua @@ -0,0 +1,38 @@ +function num_to_words(n) + local digits = {"one", "two", "three", "four", "five", + "six", "seven", "eight", "nine"} + local teens = {"eleven", "twelve", "thirteen", "fourteen", "fifteen", + "sixteen", "seventeen", "eighteen", "nineteen"} + local tens = {"ten", "twenty", "thirty", "forty", "fifty", + "sixty", "seventy", "eighty", "ninety"} + local ret = "" + if n == 1000 then return digits[1] .. "thousand" end + if n >= 100 then + local hundred = math.floor(n / 100) + ret = ret .. digits[hundred] .. "hundred" + n = n - hundred * 100 + if n > 0 then ret = ret .. "and" end + end + if n >= 10 then + if n == 10 then return ret .. tens[1] end + if n < 20 then + return ret .. teens[n - 10] + else + local ten = math.floor(n / 10) + ret = ret .. tens[ten] + n = n - ten * 10 + end + end + if n >= 1 then + ret = ret .. digits[n] + end + return ret +end + +local sum = 0 +for i = 1, 1000 do + local text = num_to_words(i) + print(i .. ": " .. text .. " (" .. text:len() .. ")") + sum = sum + text:len() +end +print(sum) diff --git a/189.lua b/189.lua new file mode 100644 index 0000000..a4ae546 --- /dev/null +++ b/189.lua @@ -0,0 +1,27 @@ +local triangle_graph = { +} + +--[[ +http://en.wikipedia.org/wiki/Graph_coloring#Computing_the_chromatic_polynomial +]] +function chromatic_polynomial(g, t) + local edge_start + for v1, edges in ipairs(g) do + for v2index, v2 in ipairs(edges) do + if v1 == v2 then return 0 end + if not edge_start then edge_start = v1 end + end + end + + if edge_start == nil then return t^#g end + + local edge_end = table.remove(g[edge_start]) + local edge_removed = chromatic_polynomial(g, t) + table.insert(g[edge_start], edge_end) + + -- need to contract the edge here + local edge_contracted = chromatic_polynomial(g, t) + -- and then fix it back up + + return edge_removed - edge_contracted +end diff --git a/2.lua b/2.lua new file mode 100644 index 0000000..d70cdc3 --- /dev/null +++ b/2.lua @@ -0,0 +1,30 @@ +local function memoize(fn) + local t = {} + return function(x) + local y = t[x] + if y == nil then y = fn(x); t[x] = y end + return y + end +end + +fib = memoize(function(n) + if n < 3 then return 1 end + return fib(n - 1) + fib(n - 2) +end) + +local root5 = math.sqrt(5) +local phi = (1 + root5)/2 +local function fib2(n) + return math.floor((phi^n-(1-phi)^n)/root5+0.5) +end + +local sum = 0 +local i = 0 +while true do + i = i + 1 + local n = fib(i) + if n > 1000000 then break end + if n % 2 == 0 then sum = sum + n end +end + +print(sum) diff --git a/2.pl b/2.pl new file mode 100755 index 0000000..6b59aed --- /dev/null +++ b/2.pl @@ -0,0 +1,18 @@ +#!/usr/bin/perl +use strict; +use warnings; + +my $root5 = sqrt 5; +my $phi = (1 + $root5)/2; + +sub fib { int (($phi**$_[0]-(1-$phi)**$_[0])/$root5 + 0.5) } + +my $i = 0; +my $sum = 0; +while (1) { + $i++; + my $n = fib $i; + last if $n > 1000000; + $sum += $n if $n % 2 == 0; +} +print "$sum\n"; diff --git a/21.lua b/21.lua new file mode 100644 index 0000000..d4a5334 --- /dev/null +++ b/21.lua @@ -0,0 +1,24 @@ +function d(n) + if n < 2 then return 0 end + local ret = 1 + local test = 2 + local limit = math.sqrt(n) + while test < limit do + if n % test == 0 then + ret = ret + test + n / test + end + test = test + 1 + end + if limit == math.floor(limit) then ret = ret + limit end + return ret +end + +local sum = 0 +for i = 1, 9999 do + local di = d(i) + if d(di) == i and i ~= di then + print(i .. ": " .. di) + sum = sum + i + end +end +print(sum) diff --git a/3.lua b/3.lua new file mode 100644 index 0000000..eff06a3 --- /dev/null +++ b/3.lua @@ -0,0 +1,8 @@ +local num = 317584931803 +local test = 3 +while true do + if num % test == 0 then num = num / test + else test = test + 2 end + if test > math.sqrt(num) then break end +end +print(num) diff --git a/3.pl b/3.pl new file mode 100755 index 0000000..7fbf7ad --- /dev/null +++ b/3.pl @@ -0,0 +1,16 @@ +#!/usr/bin/perl +use strict; +use warnings; + +my $num = 317584931803; +my $test = 3; +while (1) { + if ($num % $test) { + $test += 2; + } + else { + $num /= $test; + } + last if $test > sqrt $num; +} +print "$num\n"; diff --git a/3.sh b/3.sh new file mode 100755 index 0000000..3129d47 --- /dev/null +++ b/3.sh @@ -0,0 +1 @@ +factor 317584931803 | sed 's/.* \([[:digit:]]*\)/\1/' diff --git a/4.lua b/4.lua new file mode 100644 index 0000000..daec4bc --- /dev/null +++ b/4.lua @@ -0,0 +1,16 @@ +local function is_palindrome(n) + local first_half = string.sub(n, 1, string.len(n) / 2) + local second_half = string.sub(n, -string.len(n) / 2) + return first_half == string.reverse(second_half) +end + +local prods = {} +for i = 100,999 do + for j = 100,i do + table.insert(prods, i * j) + end +end +table.sort(prods, function(a, b) return a > b end) +for _, v in ipairs(prods) do + if is_palindrome(v) then print(v) break end +end diff --git a/5.lua b/5.lua new file mode 100644 index 0000000..b407475 --- /dev/null +++ b/5.lua @@ -0,0 +1,21 @@ +local max_factors = {} +for _, prime in ipairs({2, 3, 5, 7, 11, 13, 17, 19}) do + for i = prime, 20, prime do + local num_fact = 0 + local tmp = i + while i % prime == 0 do + num_fact = num_fact + 1 + i = i / prime + end + if num_fact > (max_factors[prime] or 0) then + max_factors[prime] = num_fact + end + end +end + +local total = 1 +for prime, power in pairs(max_factors) do + total = total * prime^power +end + +print(total) diff --git a/6.lua b/6.lua new file mode 100644 index 0000000..3c39a4b --- /dev/null +++ b/6.lua @@ -0,0 +1,13 @@ +local function sum_of_squares(n) + local total = 0 + for i = 1, n do + total = total + i^2 + end + return total +end + +local function square_of_sum(n) + return n^2*(n+1)^2/4 +end + +print(square_of_sum(100) - sum_of_squares(100)) diff --git a/7.lua b/7.lua new file mode 100644 index 0000000..d5af641 --- /dev/null +++ b/7.lua @@ -0,0 +1,19 @@ +function isprime(n) + if n < 2 then return false end + if n == 2 then return true end + if math.fmod(n, 2) == 0 then return false end + for i = 3, math.ceil(math.sqrt(n)), 2 do + if math.fmod(n, i) == 0 then return false end + end + return true +end + +local i = 2 +local primes = 0 +while true do + if isprime(i) then + primes = primes + 1 + if primes == 10001 then print(i); break end + end + i = i + 1 +end diff --git a/8.lua b/8.lua new file mode 100644 index 0000000..486ffca --- /dev/null +++ b/8.lua @@ -0,0 +1,16 @@ +local number = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450" + +local max = 0 +local index = 1 +while true do + local str = number:sub(index, index + 4) + if str:len() < 5 then break end + local prod = str:sub(1, 1) * + str:sub(2, 2) * + str:sub(3, 3) * + str:sub(4, 4) * + str:sub(5, 5) + if prod > max then max = prod end + index = index + 1 +end +print(max) -- cgit v1.2.3