157 lines
3 KiB
Ruby
157 lines
3 KiB
Ruby
# The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
|
|
#
|
|
# 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
|
|
#
|
|
# Let us list the factors of the first seven triangle numbers:
|
|
#
|
|
# 1: 1
|
|
# 3: 1,3
|
|
# 6: 1,2,3,6
|
|
# 10: 1,2,5,10
|
|
# 15: 1,3,5,15
|
|
# 21: 1,3,7,21
|
|
# 28: 1,2,4,7,14,28
|
|
#
|
|
# We can see that 28 is the first triangle number to have over five divisors.
|
|
#
|
|
# What is the value of the first triangle number to have over five hundred divisors?
|
|
#
|
|
# ----
|
|
#
|
|
# k = n(n+1)/2
|
|
# p != 2 && p|n => p|k
|
|
# p != 2 && p|n+1 => p|k
|
|
#
|
|
# p|k => p|n v p|n+1
|
|
#
|
|
# ex: k=1+2+3+4+5+6+7 = 7x8/2 = 7*2^2 => 1, 2,2^2,7,2*7, 2*2*7
|
|
# all possible combinations
|
|
#
|
|
# 0, {2}, {7}, {2,2}, {2,7}, {2,2,7}
|
|
#
|
|
# see : https://secure.wikimedia.org/wikipedia/en/wiki/Multiset
|
|
# for and explanation of multiset coefficients
|
|
#
|
|
# Méthode: 1 trouver la decomposition en nombre premiers de n puis de n+1
|
|
# enlever une puissance de deux à celui des deux qui est pair
|
|
#
|
|
# puis le nombre d'élément est une combinaison
|
|
#
|
|
#
|
|
|
|
number=500
|
|
nbprimes=200000
|
|
|
|
class PrimeGenerator
|
|
attr_accessor :limit
|
|
attr_accessor :primes
|
|
|
|
def initialize(limit=100000)
|
|
@limit=limit
|
|
self.generate
|
|
end
|
|
|
|
def generate
|
|
crosslimit=Math.sqrt(limit);
|
|
sieve=[0]*limit;
|
|
i=0;
|
|
while i<limit
|
|
sieve[i]=false
|
|
i+=1
|
|
end
|
|
i=4
|
|
while i<limit
|
|
sieve[i]=1;
|
|
i+=2
|
|
end
|
|
i=3
|
|
while i<crosslimit
|
|
if !sieve[i]
|
|
m=i*i
|
|
while m<limit
|
|
sieve[m]=true;
|
|
m+=2*i
|
|
end
|
|
end
|
|
i+=2
|
|
end
|
|
@primes=[]
|
|
i=2;
|
|
while i<limit
|
|
if not sieve[i]
|
|
@primes <<= i
|
|
end
|
|
i+=1
|
|
end
|
|
end
|
|
end
|
|
|
|
puts "Generate primes"
|
|
$primes=PrimeGenerator.new(nbprimes).primes
|
|
puts "primes generated"
|
|
|
|
def decomposition_prime(n)
|
|
res=[0]*$primes.length
|
|
i=0 # index in res
|
|
$primes.each do |p|
|
|
break if p>n
|
|
|
|
j=1 # powerfactor
|
|
while ( n % (p**j) == 0 )
|
|
j+=1
|
|
end
|
|
res[i]=j-1
|
|
|
|
i+=1
|
|
end
|
|
return res
|
|
end
|
|
|
|
def nb_multi_subset( multiset )
|
|
nb=1
|
|
multiset.each do |n|
|
|
nb *= n+1
|
|
end
|
|
return nb
|
|
end
|
|
|
|
def nbdiv(n)
|
|
if n%2 == 0
|
|
x=n/2
|
|
y=n+1
|
|
else
|
|
x=n
|
|
y=(n+1)/2
|
|
end
|
|
|
|
res=decomposition_prime(x)
|
|
res2=decomposition_prime(y)
|
|
|
|
# puts "=="
|
|
# puts x
|
|
# puts res.to_s
|
|
# puts y
|
|
# puts res2.to_s
|
|
# puts "=="
|
|
|
|
i=0
|
|
while i<res.length
|
|
res[i] += res2[i]
|
|
i+=1
|
|
end
|
|
return nb_multi_subset( res )
|
|
end
|
|
|
|
|
|
n=3637
|
|
notfound=true
|
|
while notfound
|
|
res=nbdiv( n )
|
|
puts %{#{n} (#{n*(n+1)/2}): #{res}}
|
|
if res >= number
|
|
notfound=false
|
|
break
|
|
end
|
|
n+=1
|
|
end
|
|
puts n*(n+1)/2
|
|
|