«

Paul Lutus wrote:
> Peter Hickman wrote:
>
>> Problem is that from the quiz it states that you either get a 1 or an
>> infinite loop and that an unhappy number is "obvious". Which is a sign
>> that something has not been explained clearly. Given that the Wolfram
>> page was clearer than the quiz at to what constitutes happy don't be
>> surprised if some people go off down the wrong path.
>
> As I understand the Wolfram article, an unhappy number never hits 1 as a
> result, whereas a happy number eventually hits 1:

What you have described here is the halting problem. Good luck with that.

> "Unhappy numbers have eventually periodic sequences of s(sub)i which never
> reach 1."

And what stops it from being a 1x10^50 length period, or any arbitrary
length?

> The quiz item emphasizes a criterion that is only mentioned in passing on
> the Wolfram page, that is, there are degrees of happiness, and a number
> that has many happy predecessors is, umm, more happy. So a relatively large
> number that eventually results in 1, but with a lot of steps along the way
> (therefore more happy ancestors), is happier.

And what the quiz neglected to mention is that there is an easy test for
unhappy number, which the mathworld page enumerates:

Iterating this sum-of-squared-digits map always eventually
reaches one of the 10 numbers 0, 1, 4, 16, 20, 37, 42, 58, 89,
or 145 (Sloane's A039943; Porges 1945).

So if you hit one of those unhappy numbers you know you're in an unhappy
loop.

Hans Fugal wrote:
> And what the quiz neglected to mention is that there is an easy test for
> unhappy number, which the mathworld page enumerates:
>
> Iterating this sum-of-squared-digits map always eventually
> reaches one of the 10 numbers 0, 1, 4, 16, 20, 37, 42, 58, 89,
> or 145 (Sloane's A039943; Porges 1945).
>
> So if you hit one of those unhappy numbers you know you're in an unhappy
> loop.

IMO, that's an unnecessary spoiler (which is why I didn't look at the
Wolfram page). You can figure it out on your own without a 'cheat
sheet' of numbers.

Hans Fugal wrote:

> Iterating this sum-of-squared-digits map always eventually
> reaches one of the 10 numbers 0, 1, 4, 16, 20, 37, 42, 58, 89,
> or 145 (Sloane's A039943; Porges 1945).

As long as we're noting strategy, the site also noted that 16 and 61 are
identical in terms of the next number. Any set of digits can be
scrambled any which way and it won't matter. 61 will eventually work
around to 16 also. (As shown by the proof of 3, earlier.)

--
Posted via http://www.ruby-forum.com/.

On 9/1/06, Hans Fugal <> wrote:
> Paul Lutus wrote:
> > Peter Hickman wrote:
> >
> >> Problem is that from the quiz it states that you either get a 1 or an
> >> infinite loop and that an unhappy number is "obvious". Which is a sign
> >> that something has not been explained clearly. Given that the Wolfram
> >> page was clearer than the quiz at to what constitutes happy don't be
> >> surprised if some people go off down the wrong path.
> >
> > As I understand the Wolfram article, an unhappy number never hits 1 as a
> > result, whereas a happy number eventually hits 1:
>
> What you have described here is the halting problem. Good luck with that.

Something which reduces to HP is not equivalent to HP, only if you can
reduce HP to this problem is it equivalent to HP/undecidable.

> > "Unhappy numbers have eventually periodic sequences of s(sub)i which never
> > reach 1."
>
> And what stops it from being a 1x10^50 length period, or any arbitrary
> length?

Basic math does.
number of length 100 : 99999...., next step = 100*9^2 = 8100, i.e.
large numbers always go down _a lot_, and therefore cannot be part of
a cycle.
Proving this for n >= 243 (or even smaller n) is left as an exercise
for the reader

On 9/1/06, Hans Fugal <> wrote:
> Paul Lutus wrote:
> > "Unhappy numbers have eventually periodic sequences of s(sub)i which never
> > reach 1."
>
> And what stops it from being a 1x10^50 length period, or any arbitrary
> length?

The period cannot be any larger than 1000. The largest period is
probably quite a bit smaller than this, but this is a upper bound.
Why?

Some definitions, first.

Let's define g(x) as the function that takes a number to it's
successor. For example, g(42) = 4^2 + 2^2 = 20.

For a variable x, we will denote the result of applying our function
as x'. That is, x' = g(x).

Let Mi = 10^i - 1 for all i. For example, M4 = 9999. Each Mi is the
number made up of i nines. Mi' is then 81 * i.

Let Qi = { x | M(i-1) < x <= Mi }. For example, Q4 is the range of
integers from 1000 to 9999. It's easy to see that the union of all
Qi's cover the natural numbers and that they are all disjoint. So the
set of all Qi's is a partitioning of the natural numbers.

For each x in Qi, it is easy to see that x' <= Mi'.

Now, take any i >= 4. For all x in Qi, x' <= Mi' = 81 * i. But 81 * i
< 10^(i-1) (see below), so 81 * i <= M(i-1), and x' <= M(i-1) for all
x in Qi. But since x > M(i-1) by our choice, we know that x' < x. This
is true for *all* x > 999.

So, for those of you glossing over the math, the conclusion is that
applying the "happy function" to any number greater than or equal to
1000 will necessarily result in a smaller number.

Since the sequence can't loop if we're constantly decreasing (until we
get down to 999 or less), none of the numbers in a period can be
greater than 999 -- there's no way to get back *up* to any of those
numbers.

So, for any loop resulting from a number, the space of numbers liable
to be in that loop is no larger than 1000 number (0 through 999). So
no loop can have a period greater than 1000.

Jacob Fugal

Phrogz wrote:
> Hans Fugal wrote:
>> And what the quiz neglected to mention is that there is an easy test for
>> unhappy number, which the mathworld page enumerates:
>>
>> Iterating this sum-of-squared-digits map always eventually
>> reaches one of the 10 numbers 0, 1, 4, 16, 20, 37, 42, 58, 89,
>> or 145 (Sloane's A039943; Porges 1945).
>>
>> So if you hit one of those unhappy numbers you know you're in an unhappy
>> loop.
>
> IMO, that's an unnecessary spoiler (which is why I didn't look at the
> Wolfram page). You can figure it out on your own without a 'cheat
> sheet' of numbers.
>

This isn't a math quiz. It's a programming quiz.

On 9/1/06, Jacob Fugal <> wrote:
> Now, take any i >= 4. For all x in Qi, x' <= Mi' = 81 * i. But 81 * i
> < 10^(i-1) (see below), so 81 * i <= M(i-1), and x' <= M(i-1) for all
> x in Qi. But since x > M(i-1) by our choice, we know that x' < x. This
> is true for *all* x > 999.

And here's the "below" referred to (I forgot it earlier).

Remember that i >= 4. Let's take i = 4 as a basis case.

81 * 4 = 324 < 1000 = 10^(4-1)

Now, assume the hypothesis for some i >= 4. We will prove the
hypothesis continues to hold for j = i + 1.

Since 1/9 < i; 81 < 9 * 81 * i.
Adding 81 * i to both sides of that inequality we get:
81 * j < 10 * 81 * i

From the other side, we can start with the inequality for i (81 * i <
10^(i-1)) and multiply both sides by 10 to get:
10 * 81 * i < 10^(j-1)

Combining those two inequalities, we have: 81 * j < 10^(j-1).

Isn't induction great?

Jacob Fugal

Jacob Fugal wrote:
> On 9/1/06, Hans Fugal <> wrote:
>> And what stops it from being a 1x10^50 length period, or any arbitrary
>> length?
>
> The period cannot be any larger than 1000. The largest period is
> probably quite a bit smaller than this, but this is a upper bound.
> Why?

<mathematical proof proof />

> So, for those of you glossing over the math, the conclusion is that
> applying the "happy function" to any number greater than or equal to
> 1000 will necessarily result in a smaller number.
>
> Since the sequence can't loop if we're constantly decreasing (until we
> get down to 999 or less), none of the numbers in a period can be
> greater than 999 -- there's no way to get back *up* to any of those
> numbers.
>
> So, for any loop resulting from a number, the space of numbers liable
> to be in that loop is no larger than 1000 number (0 through 999). So
> no loop can have a period greater than 1000.

And that, my friends, is what stops it from being a 1x10^50 length
period, or any arbitrary length.

If the intent of the quiz was to be mathemeticians and figure all this
mathy stuff out, I apologize for dragging it into the open.

Paul Lutus wrote:
> Another example is non-Euclidean geometry, which was an impractical,
> exotic
> plaything for about 100 years, until general relativity came along and
> required it. Without non-Euclidean geometry, Einstein wouldn't have been
> able to express GR at all.
>
> Prior to that, few would have guessed that the universe isn't Euclidean.

Wait, are you suggesting that in a hundred years, Happy Numbers could
prove the universe is... Happy?

--
Posted via http://www.ruby-forum.com/.

Here's my solution. Writing a method that can determine whether a number is
happy, and how happy it is, is fairly simple. Once the method exists, it's
fairly trivial to write short programs that use the method to determine the
happiness of a number, or to find the highest happy number or the happiest
number in a range, as requested by the quiz. But the Ruby Quiz generally
requests that you write a program, not a single method, so I decided to write a
program that can perform all of these tasks, depending on the input parameter.
And handle bases other than ten if desired, to boot.

Once I decided to do that, it made sense to optimize the method over multiple
runs, by memoizing results, and taking algorithmic shortcuts based on previously
memoized results. So my get_happy method is a bit more complicated than it was
originally, due to the optimizations.

Of course, once I added optimizations, I introduced bugs. They were subtle and a
bit tricky to track down. But they basically boiled down to this question: Is 1
a happy number, and if so, how happy? It's obvious that when you perform one
iteration of the happiness algorithm, the next number in the sequence has a
happiness value of one less than the current number. For example, take the
sequence used in the quiz description. It starts with 7, which is finally stated
to have a happiness value of 4. The remaining numbers in the sequence, 49, 97,
130, and 10, thus have happiness values of 3, 2, 1, and 0 respectively.

So, is 1 happy? If the definition of a happy number is that the algorithm
evenually reaches 1, then yes it is. What is its happiness value? It could
arguably be 0, because the algorithm goes to 1 right away, without generating
any other happy numbers. But, any number with a happiness value of 0, such as
10, has 1 as its next iterated value, which means that, according to the
paragraph above, 1 should have a happiness value of 1 less than 0, which would
be -1. So is 1's happiness value 0 or -1?

I guess it's an arbitrary choice. But until I realized what was going on, I had
a bug in which a number's happiness value would either be correct, or 1 higher
than correct, depending on whether or not it was being calculated based on a
previous memoized intermediate value. I had originally set 1's happiness value
to 0, but this caused 10's value to be calculated as 1 instead of 0, because it
was 1 higher than the happiness value of the next number in the sequence, which
was of course 1, whose happiness is 0. This happened only when 10's happiness
value was memoized during another number's sequence, but not when 10 itself had
been passed into the get_happy method. Then I naively changed 1's happiness
value to -1, to try to fix this. But this didn't work either, since -1 is my
magic value meaning "unhappy", so all numbers were determined to be unhappy
since 1's memoized value returned as -1 in the first optimization. So I changed
1's happiness value back to 0, and unconditionally decreased all numbers'
happiness values by 1, which also turned out to be wrong.

When I finally understood what was going on, I realized that the correct fix was
to add the "(temp != 1)" conditional in the first "if" statement, and the "ret
-= 1" line if the algorithm has iterated all the way to 1. At this point, 1's
happiness value isn't actually used in the algorithm for computing any other
number's happiness. It's only ever used if get_happy is called on the value 1
itself. And at last, the program works! (At least, I'm pretty sure it does )

#!/usr/bin/env ruby
#
# =Description
#
# This program determines the happiness of a number, or the happiest number and
# highest happy number in a range of numbers.
#
# A number's happiness is determined as follows: Sum the squares of the number's
# individual digits. Repeat this process with the result, until a value of 1 is
# reached, or until a value is repeated, thus indicating a loop that will never
# reach 1. A number for which 1 is reached is "happy". The number of other
# numbers generated besides 1 and the original number is its happiness value.
#
# =Usage
#
# happy.rb num1[-num2][:base]
#
# happy.rb takes a single argument. If the argument is a single number, that
# number's happiness value is displayed, or the number is said to be unhappy.
# If the argument is a range of numbers, such as "1-400", the happiness value of
# the happiest number (lowest number breaking ties) in that range is returned.
# If the argument ends with a colon and a number, such as "50:8" or "1-100:2",
# the number after the colon specifies the base of the first number(s). An
# unspecified base implies base ten.

require 'rdoc/usage'

#================================================= =============================
# ----- Global variables -----
#================================================= =============================

$hap_map = {} # Hash for memoization of happiness values

#================================================= =============================
# ----- Instance methods -----
#================================================= =============================
class String
# Indicates whether the string is a valid number of the specified base.
def is_num_of_base?(base)
# sub() call removes leading zeros for comparison
self.sub(/\A0+/, '').downcase == self.to_i(base).to_s(base).downcase
end
end

class Integer
# Pretty-print string including base, if base is not 10
def pretty(base)
self.to_s(base) + ((base == 10) ? "" : " (base #{base})")
end
end

#================================================= =============================
# ----- Global methods -----
#================================================= =============================

# This method returns the happiness value of the given number. A value of -1
# indicates that the number is unhappy.
def get_happy(num, base=10)
$hap_map[num] = 0 if num == 1 # Handles trivial case
return $hap_map[num] if $hap_map[num]

ret = 0
done = false
inters = []
temp = num

until done
digits = temp.to_s(base).split(//).map{|c| c.to_i(base)}
temp = digits.inject(0) {|sum, d| sum + d**2}
ret += 1

if (temp != 1) && $hap_map[temp]
# Optimization; use knowledge stored in $hap_map
if $hap_map[temp] == -1
ret = -1
done = true
else
ret += $hap_map[temp]
done = true
end
else
if temp == 1
ret -= 1 # Don't count 1 as an intermediate happy number
done = true
elsif inters.include?(temp)
ret = -1
done = true
else
inters << temp
end
end
end

$hap_map[num] = ret

# Optimization
if ret == -1
# If num is not happy, none of the intermediates are happy either
inters.each {|n| $hap_map[n] = -1}
else
# If num is happy, each intermediate has a happiness value determined by
# its position in the array
inters.each_index {|idx| $hap_map[inters[idx]] = (ret - 1) - idx}
end

return ret
end

# nums is a range of integers. This method returns two values: the happiest
# number, and the highest happy number, in the range. Two nil values will be
# returned if there are no happy numbers in the range.
def get_superlatives(nums, base)
happiest_num = nil
happiest_ness = nil
highest = nil

nums.each do |n|
happy = get_happy(n, base)
next if happy == -1
highest = n

if (!happiest_ness) || (happy > happiest_ness)
happiest_num = n
happiest_ness = happy
end
end

return happiest_num, highest
end

#================================================= =============================
# ----- Script start -----
#================================================= =============================

if ARGV.size != 1
RDoc.usage('Usage', 'Description')
end

# Parse arg
ARGV[0] =~ /\A([\d\w]+)(?:\-([\d\w]+))?(?:\d+))?\Z/
num1, num2, base = $1, $2, $3

# Ensure legal arg
RDoc.usage('Usage', 'Description') unless num1

# Fill in defaults
base = 10 unless base
num2 = num1 unless num2

# Convert numbers from strings to numeric values
base = base.to_i

[num1, num2].each do |s|
unless s.is_num_of_base?(base)
puts "Error: #{s} is not a valid base #{base} number"
exit
end
end

num1 = num1.to_i(base)
num2 = num2.to_i(base)

# Calculate and print results
if num1 == num2
happiness = get_happy(num1, base)

print num1.pretty(base)

if happiness == -1
print " is not happy.\n"
else
print " has a happiness of #{happiness}\n"
end
else
if num1 > num2
num1, num2 = num2, num1
end

happiest, highest = get_superlatives((num1..num2), base)

if !highest
puts "None of those numbers are happy."
else
puts "The happiest number is " + happiest.pretty(base) +
", with a happiness of #{get_happy(happiest, base)}"

puts "The highest happy number is " + highest.pretty(base) +
", with a happiness of #{get_happy(highest, base)}"
end
end

--
Karl von Laudermann - karlvonl(a)rcn.com - http://www.geocities.com/~karlvonl
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Compl ex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?" ":"@@");puts if x==w-1;}}