Reply to thread

Message: [QUOTE="Sander Land, post: 4525527"] I solved the question of the happiness of 1 by simply giving 10 and such a happiness of 2, and 7 a happiness of 5. This doesn't matter for determining the happiest number anyway, and is a bit more consistent. For finding the happiest numbers it only searches numbers with non decreasing digits (eg. 123 but not 312 and 321). This speeds up the search a lot, it can handle searching up to 10^10 in seconds. It can also search for happy bases, because of this my solution has to work for any base and is a bit messy as to_s is useless for this and recursion is impossible for bases above 250 or so (stack overflow and such). To speed up searches it doesn't clear the cache from previous bases, so memory uses increases until 300Mb at base 3000 or so. Anyway, the world is a better place now that we know there are no happy bases under 3202 ;) Usage: happy.rb find [base] - find the happiest number under base^7 happy.rb without parameters: search for happy bases Code: class Array def sum inject(0){|a,b| a+b} end end class Integer def to_digits(base) return [self] if self < base (self/base).to_digits(base) << self%base end def happy_function to_digits($base).map{|d| d ** 2}.sum end def happiness num = self chain = [num] until num == 1 || num.cached_happiness == -1 num.cached_happiness = -1 chain << num = num.happy_function end if num == 1 chain.shift.cached_happiness = chain.size until chain.empty? end self.cached_happiness end def happy? happiness >= 0 end protected def cached_happiness return 0 if self==1 (@happiness||={})[$base] end def cached_happiness=(val) (@happiness||={})[$base] = val end end def nondec_nums(len,min=0,n=0,&b) # yields all numbers with non-decreasing digit sequences of length <= len if len==0 yield n else [*min...$base].each{|m| nondec_nums(len-1, m ,n * $base + m,&b) } end end maxn = maxh = 1 s = Time.now if ARGV[0] == 'find' $base = (ARGV[1] || 10 ).to_i MAXLEN = 7 puts "searching happiest number < #{$base**MAXLEN} in base #{$base}" max_n, max_h = 1,0 nondec_nums(MAXLEN) {|n| # length 7 / up to 9,999,999 if n.happiness > max_h max_n, max_h = n, n.happiness puts "n=#{n}\th=#{max_h}\tdigits=#{n.to_digits($base).inspect}" end } else puts "searching for happy bases, press ctrl-c to quit" (2..1_000_000).each {|$base| len = 3 # len * (base-1)^2 < b^len - 1 for len >= 3 and any base max = $base**len - 1 # upper bound for when \forall n>=max n.happy_function < n => if all numbers of up to and including this length are happy then all numbers are max -= $base**(len-1) while max.happy_function < max # further decrease upper bound, for base 10 this is : 999, 899, 799, etc max += $base**(len-1) # previous loop always does 1 step too much happy_base = true min_unhappy = nil nondec_nums(len) {|n| if !n.happy? && n>0 min_unhappy = n happy_base = false break end break if n > max } puts happy_base ? "base #{$base} is a happy base!" : "base #{$base} is not a happy base because #{min_unhappy} is unhappy." } end [/QUOTE]

Verification