Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 334 lines (294 sloc) 7.707 kB
ddeeda8 @tardate added MyMath.rb
authored
1 # my collection of routines built up while solving problems
2 # at projecteuler.net
3 # By Paul Gallagher gallagher.paul@gmail.com
4 # http://tardate.blogspot.com
5 # free to share and use anyhow, anywhere...
6 #
74a3a62 @tardate added MyMath.rb
authored
7 class Integer
8
9 # @see project euler #15,20,34
10 def factorial
11 (2..self).inject(1) { |prod, n| prod * n }
12 end
13
14 # sum of digits in the number, expressed as a decimal
15 # @see project euler #16, 20
16 def sum_digits
17 self.to_s.split('').inject(0) { |memo, c| memo + c.to_i }
18 end
19
20 # num of digits in the number, expressed as a decimal
21 # @see project euler #25
22 def num_digits
23 self.to_s.length
24 end
25
26 # returns an array of all the base10 digit rotations of the number
27 # @see project euler #35
28 def rotations
29 self.to_s.rotations.collect { |s| s.to_i }
30 end
31
32 # tests if all the base10 digits in the number are odd
33 # @see project euler #35
34 def all_digits_odd?
35 self.to_s.split('').inject(0) { |memo, s| memo + ( s.to_i%2==0 ? 1 : 0 ) } == 0
36 end
37
38 # @see project euler #4, 36, 91
39 def palindrome?(base = 10)
40 case base
41 when 2
42 sprintf("%0b",self).palindrome?
43 else
44 self.to_s.palindrome?
45 end
46 end
47
48 # http://en.wikipedia.org/wiki/Prime_factor
49 # @see project euler #12
50 def prime_factors
51 primes = Array.new
52 d = 2
53 n = self
54 while n > 1
55 if n%d==0
56 primes << d
57 n/=d
58 else
59 d+=1
60 end
61 end
62 primes
63 end
64
65 # http://en.wikipedia.org/wiki/Divisor_function
66 # @see project euler #12
67 def divisor_count
68 primes = self.prime_factors
69 primes.uniq.inject(1) { |memo, p| memo * ( ( primes.find_all {|i| i == p} ).length + 1) }
70 end
71
72 #
73 # @see project euler #12, 21, 23
74 def divisors
75 d = Array.new
76 (1..self-1).each { |n| d << n if self % n == 0 }
77 d
78 end
79
80 # @see project euler #
81 def prime?
82 divisors.length == 1 # this is a brute force check
83 end
84
85 # prime series up to this limit, using Sieve of Eratosthenes method
86 # http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
87 # @see project euler #7, 10, 35
88 def prime_series
89 t = self
90 limit = Math.sqrt(t)
91 @a = (2..t).to_a
92 n = 2
93 while (n < limit) do
94 x = n*2
95 begin
96 @a[x-2]=2
97 x+=n
98 end until (x > t )
99 begin
100 n+=1
101 end until ( @a[n-2] != 2 )
102 end
103 @a.uniq!
104 end
105
106 # @see project euler #23
107 def perfect?
108 self == divisors.sum
109 end
110
111 # @see project euler #23
112 def deficient?
113 self > divisors.sum
114 end
115
116 # @see project euler #23
117 def abundant?
118 self < divisors.sum
119 end
120
121 # http://en.wikipedia.org/wiki/Collatz_conjecture
122 # @see project euler #14
123 def collatz_series
124 @a = Array.new
125 @a << n = self
126 while n > 1
127 if n % 2 == 0
128 n /= 2
129 else
130 n = 3*n + 1
131 end
132 @a << n
133 end
134 @a
135 end
136
137 # express integer as an english phrase
138 # @see project euler #17
139 def speak
140 case
141 when self <20
142 ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
143 "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" ][self]
144 when self > 19 && self < 100
145 a = ["twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"][self / 10 - 2]
146 r = self % 10
147 if r == 0
148 a
149 else
150 a + "-" + r.speak
151 end
152 when self > 99 && self < 1000
153 a = (self / 100).speak + " hundred"
154 r = self % 100
155 if r == 0
156 a
157 else
158 a + " and " + r.speak
159 end
160 when self > 999 && self < 10000
161 a = (self / 1000).speak + " thousand"
162 r = self % 1000
163 if r == 0
164 a
165 else
166 a + ( r <100 ? " and " : " " ) + r.speak
167 end
168 else
169 self
170 end
171 end
172
173 # generates triangle number for this integer
174 # @see project euler #42
175 def triangle
176 self * ( self + 1 ) / 2
177 end
178
179 # calculates integer partitions for given number using array of elements
180 # http://en.wikipedia.org/wiki/Integer_partition
181 # @see project euler #31
182 def integer_partitions(pArray, p=0)
183 if p==pArray.length-1
184 1
185 else
186 self >= 0 ? (self - pArray[p]).integer_partitions(pArray ,p) + self.integer_partitions(pArray,p+1) : 0
187 end
188 end
189
190 end
191
192 class Array
193
194 # sum elements in the array
195 def sum
196 self.inject(0) { |sum, n| sum + n }
197 end
198
199 # sum of squares for elements in the array
200 # @see project euler #6
201 def sum_of_squares
202 self.inject(0) { |sos, n| sos + n**2 }
203 end
204
205 # @see project euler #17
206 def square_of_sum
207 ( self.inject(0) { |sum, n| sum + n } ) ** 2
208 end
209
210 # index of the smallest item in the array
211 def index_of_smallest
212 value, index = self.first, 0
213 self.each_with_index {| obj, i | value, index = obj, i if obj<value }
214 index
215 end
216
217 # removes numbers from the array that are factors of other elements in the array
218 # @see project euler #5
219 def remove_factors
220 @a=Array.new
221 self.each do | x |
222 @a << x if 0 == ( self.inject(0) { | memo, y | memo + (x!=y && y%x==0 ? 1 : 0) } )
223 end
224 @a
225 end
226
227 # http://utilitymill.com/edit/GCF_and_LCM_Calculator
228 # @see project euler #5
229 def GCF
230 t_val = self[0]
231 for cnt in 0...self.length-1
232 num1 = t_val
233 num2 = self[cnt+1]
234 num1,num2=num2,num1 if num1 < num2
235 while num1 - num2 > 0
236 num3 = num1 - num2
237 num1 = [num2,num3].max
238 num2 = [num2,num3].min
239 end
240 t_val = num1
241 end
242 t_val
243 end
244
245 # http://utilitymill.com/edit/GCF_and_LCM_Calculator
246 # @see project euler #5
247 def LCM
248 a=self.remove_factors
249 t_val = a[0]
250 for cnt in 0...a.length-1
251 num1 = t_val
252 num2 = a[cnt+1]
253 tmp = [num1,num2].GCF
254 t_val = tmp * num1/tmp * num2/tmp
255 end
256 t_val
257 end
258
259 # brute force method:
260 # http://www.cut-the-knot.org/Curriculum/Arithmetic/LCM.shtml
261 # @see project euler #5
262 def lcm2
263 a=self.remove_factors
264 c=a.dup
265 while c.uniq.length>1
266 index = c.index_of_smallest
267 c[index]+=a[index]
268 end
269 c.first
270 end
271
272 # returns the kth Lexicographical permutation of the elements in the array
273 # http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation
274 # @see project euler #24
275 def lexicographic_permutation(k)
276 k -= 1
277 @s = self.dup
278 n = @s.length
279 n_less_1_factorial = (n - 1).factorial # compute (n - 1)!
280
281 (1..n-1).each do |j|
282 tempj = (k / n_less_1_factorial) % (n + 1 - j)
283
284 @s[j-1..j+tempj-1]=@s[j+tempj-1,1]+@s[j-1..j+tempj-2] unless tempj==0
285 n_less_1_factorial = n_less_1_factorial / (n- j)
286 end
287 @s
288 end
289
290 # returns ordered array of all the lexicographic permutations of the elements in the array
291 # http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation
292 # @see project euler #24
293 def lexicographic_permutations
294 @a=Array.new
295 (1..self.length.factorial).each { |i| @a << self.lexicographic_permutation(i) }
296 @a
297 end
298
299 end
300
301 class String
302
303 # sum of digits in the number
304 # @see project euler #16, 20
305 def sum_digits
306 self.split('').inject(0) { |memo, c| memo + c.to_i }
307 end
308
309 # product of digits in the number
310 # @see project euler #8
311 def product_digits
312 self.split('').inject(1) { |memo, c| memo * c.to_i }
313 end
314
315 #
316 # @see project euler #4, 36, 91
317 def palindrome?
318 self==self.reverse
319 end
320
321 # returns an array of all the character rotations of the string
322 # @see project euler #35
323 def rotations
324 s = self
325 @rotations = Array[s]
326 (1..s.length-1).each do |i|
327 s=s[1..s.length-1]+s[0,1]
328 @rotations << s
329 end
330 @rotations
331 end
332
333 end
Something went wrong with that request. Please try again.