Newsgroups: rec.puzzles, sci.math
Followup-To: sci.math
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 8 May 91 18:20:09 GMT
Subject: Re: Name this property

ma...@cs.fsu.edu (Bill Mayne) writes:

>A few years ago in an amateur (very amateur) number theory discussion
>group on a bulletin board Walter Nissen proposed the following
>challenge:
>  Find all natural numbers which have a binary representation
>  that ends in a string of digits identical to the decimal
>  representation.  E.g., the binary representation of 101 is
>  1100101, which ends 101.

Nice problem.

>In the first place it is obvious that there are an infinite number of
>such numbers, so finding them all is out of the question.

You can certainly describe the infinite set in instructive ways.  For
instance, ``The tens and hundreds digits are arbitrary (1 or 0) for
numbers up to five digits, must be equal for six or seven digits,
and must be zero for more digits.''  This might lead to an algebraic
structure, or at least good bounds on how many such numbers there are
below 10^n.

>...there is a very efficient algorithm for enumerating all the
>examples up to a given size.

Does your algorithm generalize to other bases?  Base 5 should be easy.
Base 4 is probably tricky.  Base 3 may get real tough.

>(Up to 32 digits, the limit of integer size with most C compilers on
>PCs, ...)

Ick.  You need some bignums.  Or maybe just vectors of digits.  But
something, because the interesting things don't start happening until
about 10^14.

>As far as I know this was just something Mr. Nissen dreamed up. My
>question is: Is there a name for this property?

I suggest ``polyradicism''.

>Is there any area of theory which resembles this type of thing?

I don't know.  Let me know what you find out.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil