NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/math/9439

Text File | 1992-07-22 | 1.9 KB | 46 lines

Newsgroups: sci.math
Path: sparky!uunet!elroy.jpl.nasa.gov!usc!sol.ctr.columbia.edu!destroyer!ncar!unmvax!mimbres.cs.unm.edu!nmt.edu!news
From: [e-mail] (Jeff Putnam)
Subject: run the hailstone backwards...
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: akbar
Organization: New Mexico Institute of Mining & Technology
Date: Wed, 22 Jul 1992 13:46:01 GMT
Lines: 34


I was thinking the other day about the hailstone numbers
(or whichever name you prefer to use) and thought about running
them backwards as a programming exercise.  I wanted to
give the numbers n and m and produce the m smallest precursors
(a precursor to n is a number k, such that f(k), f(f(k)), and
so on eventually includes n) to n _in_ _ascending_ _order_.
That is, given (say) 5, we have 10, 20, 40... as precursors,
and 10 has 3 as a precursor, so 3 gives us 6, 12.... (this
branch will never get smaller) and so on.  So 5 has (at least)
3,6,10,12 as precursors

Now, each number n has at least one immediate precursor (2n)
and then all the doubles of this.  If n=3k+1, then n has
precursors 2n and k.  If n=3k+2, it only has one precursor
(2(3k+2)=3(2k+1)+1), but that precursor has two precursors,
one of which (2k+1) is less than n.

So, to compute all the precursors we want to develop this
tree.  This doesnt give us the precursors of n in ascending
order.  If we always try the subtract-one-and-divide-by-3
subtree first, we get smaller numbers, but there is still
the possibility that by going out one of the multiply-by-2
branches we will arrive at a number that is a multiple iterate
of the 3n+1 branch.  (That is, it is 3n+1, where n is 3k+1 and
k is 3j+1 and so on.)

So, my question is, is there a way to figure out which branches
of the tree are best to explore in order to generate the
m smallest precursors to n?

--
jefu <=> Jeff Putnam - New Mexico Tech <=> [e-mail]
"Overturn the dominant paradigm"