[seqfan] Re: PS and SP numbers (bis)

Fri Apr 29 15:22:19 CEST 2005

> At any rate, the finity argument goes as follows.

Wow.  I would probably have never figured this out on my own, though I spent 
a couple hours last night trying.  I think I was on the right track though. 
You pros blow my mind with your brainpower.  :-)

> At any rate, the finity argument goes as follows.
> Let |n|, s(n), and p(n) be the number, sum, and
> product of the base-10 digits of n.  For SP
> numbers, we have n = s(n) concat p(n), so that
> |n| = |s(n)| + |p(n)|.

Okay so "|x|" = "the number of digits of x" as opposed to "the absolute 
value of x"?

When I started trying to figure this out myself  this was the path I was 
going down.  I asked myself, for x (a number of N digits), what is the 
maximum length of s(x) and p(x)? Both maximums are achieved when x is 
composed entirely of 9's.  This means the maximum s(x) for an N digit number 
is 9*N and the maximum p(x) is 9^N.  But the maximum p(x) for an N digit 
number at least early on is N digits, if .  I tested exponents up to 15 and 
then took a different, complex, and ultimately erroneous tack.

If I had pushed on, I would have found that 9^N does not always have N 
digits--at some point |9^N| < N.  And continuing on there is a point where 
|9^N| + |9*N| < N.  As you note that happens at 88 digits.  9^88 is 84 
digits long.  9*88 is 3 digits long.  84 + 3 = 87 which is less than 88, so 
there can be no 88 digit SP number.

If I push on to the point where s(9*N) is 4 digits to try and make up for 
that missing digit, I end up at N=112.  But in the meantime the gap between 
|9^N| and N has grown.  |9*112| = 4 but |9^112| = 107.  107 + 4 = 111 which 
is still less than 112.

By the time |9*N| reaches 5 (at N = 1112), the gap between |9^N| and N has 
increased to 50 digits (|9^N| = 1062).  Clearly there is no hope of |9^N| + 
|9*N| >= N when N >= 88.

Thanks!

                    -- Chuck

PS: BTW, shouldn't A062237 include 0?  s(0) = 0, p(0) = 0, and the 
concatenation of the two is 00 which is numerically equivalent to 0 so isn't 
0 an SP number?

----- Original Message ----- 
From: "David Wilson" <davidwwilson at comcast.net>
To: "Chuck Seggelin" <seqfan at plastereddragon.com>
Cc: "Sequence Fans" <seqfan at ext.jussieu.fr>
Sent: Friday, April 29, 2005 6:32 AM
Subject: Re: [seqfan] Re: PS and SP numbers (bis)

Yes, in addition to noting that A062237 is finite, I also found the two
additional
elements that you found, and updated the sequence accordingly.  Also, I
noted
that the sequence was base-dependent.

At any rate, the finity argument goes as follows.  Let |n|, s(n), and p(n)
be the
number, sum, and product of the base-10 digits of n.  For SP numbers, we
have
n = s(n) concat p(n), so that |n| = |s(n)| + |p(n)|.  But for |n| >= 88,
|s(n)|+|p(n)| < |n|,
so no number of 88 or more digits is an SP number.

There is also a heuristic argument that we shouldn't find too many SP
numbers.

Let n be an SP number.  If n has the digit 0, p(n) = 0, and n = s(n) concat
0.
Thus s(n) = s(s(n) concat 0) = s(s(n)).   If s(n) >= 10, s(s(n)) < s(n), so
s(n) <= 9.
This gives n = s(n) concat 0 = 10s(n) <= 90.  No SP number > 90 includes the
digit 0.  The rest of this message assumes n > 90.

Suppose n is an SP number.  Suppose p(n) includes the digit 0.  Then
n = s(n) concat p(n) includes 0, and by the previous paragraph, n is not SP.
The contradiction shows p(n) does not include 0.  This p(n) cannot end in 0,
so that 10 does not divide p(n), and p(n) cannot contain both an even digit
and a 5.

Now note that p(n), being the product of decimal digits, is a 7-smooth
number,
that is, of the form 2^a 3^b 5^c 7^d.  Large numbers of this form will tend
to
include the digit 0.  Just as it is all but certain that sufficiently large
powers of 2
include the digit 0, the same can be said of sufficiently large 7-smooth
numbers.
Thus, in the absence of the proven 87-digit limit, we would be safe to
conjecture
that there are a finite number of SP numbers.  From a practical standpoint,
this
phenomenon kicks in way below 88 digits, I would be amazed if there were
an SP number of 20 or more digits.

Final note.  As I said before, p(n) is of the form 2^a 3^b 5^c 7^d.  Since
p(n)
cannot end in 0, 10 does not divide p(n), so p(n) = 2^a 3^b 7^c or 3^a 5^b
7^c.
It is computationally feasible to generate every p(n) of this form <= 87
digits.
Given p(n), s(n) = s(s(n))+s(p(n)) should allow us to find close bounds on
s(n).  This means that computing all necessary candidate pairs (s(n), p(n))
should be computationally feasible.  This would make it possible to find
every
element of this sequence, just as I was able to find every element of
A038369
(the sum-product numbers, defined as n = s(n)p(n) as opposed to s(n) concat
p(n)).

----- Original Message ----- 
From: "Chuck Seggelin" <seqfan at plastereddragon.com>
To: <ham>; "David Wilson" <davidwwilson at comcast.net>; "Eric Angelini"
<keynews.tv at skynet.be>; <ham at jussieu.fr>; <seqfan at ext.jussieu.fr>
Sent: Thursday, April 28, 2005 4:33 PM
Subject: Re: [seqfan] Re: PS and SP numbers (bis)

>I assume that although it is finite, not all the terms have been given?
>
> I say this because unless I'm mistaken, the 17'th and 18'th terms of this 
> sequence should be:
>
> 3634992 (digits sum to 36, product is 34992)
> 43139968 (digits sum to 43, product is 139968)
>
> Are there any terms beyond 43139968?
>
>            -- Chuck
>
>
> ----- Original Message ----- 
> From: "David Wilson" <davidwwilson at comcast.net>
> To: "Eric Angelini" <keynews.tv at skynet.be>; <ham at jussieu.fr>; 
> <seqfan at ext.jussieu.fr>
> Sent: Thursday, April 28, 2005 3:15 PM
> Subject: [seqfan] Re: PS and SP numbers (bis)
>
>
> BTW, A062237 is finite.
>
>
> ----- Original Message ----- 
> From: "Eric Angelini" <keynews.tv at skynet.be>
> To: <ham>; <seqfan at ext.jussieu.fr>
> Sent: Thursday, April 28, 2005 10:37 AM
> Subject: PS and SP numbers (bis)
>
>
>> Sorry, it is A062237
>>
>> à+
>> É.
>> __________________________________________________
>> http://angelink.be/?CeRaccourciFaitCinquanteSignes
>>
>
>
> --------------------------------------------------------------------------------
>
>
> No virus found in this incoming message.
> Checked by AVG Anti-Virus.
> Version: 7.0.308 / Virus Database: 266.10.4 - Release Date: 4/27/2005
>
> 