Short & Sweet Math Challenge #17: The Feast !

Hi all,

Several months have merrily passed by since I posted my previous S&SMC#16 and
now it's as good time as any to post my brand-new Short & Sweet Math Challenge #17:
The Feast!
, arranged meal-like, so to say. Dust off once more what's left of your
HP-calc programming skills (if any) and enjoy ... Bon appetit !

Important: Rules & Notes:

• In all cases, you must write a program for your chosen HP handheld preferably, but other
brands are also acceptable as long as they're handheld (but no PDAs), emulators/simulators for such models
are also welcome. Any programming language is acceptable as long as it actually runs in your
chosen handheld.

• Please absolutely refrain from posting just the solutions, actual code written by yourself *is* mandatory
. Googling solutions out and copy-posting them is pretty lame and only serves to
spoil the challenge for others and to make blatantly public your utter lack of programming skills and/or
sheer disrespect for fair rules and this forum's visitors.

## Appetizer: More power to you

"Write a program to find the first exact power of 2 (up to 22500, say) that begins with a given
sequence of up to four digits"

For instance, if the given sequence is 102 your program
should output 10, as 210 = 1024. You can either
give just the required exponent (10), or also output the power itself (1024),
for extra élan.

Use your program to find (and output) the first exact power of 2 which begins with
1000, 1234, 1313, 2006, and 1776.

I'll give both a fast 3-line HP-71B program for the easier case, and a still simple, fairly fast program for the more elaborate second case.

## Main course: Le petit homage to the 41 !

"Find a 41-digit number consisting solely of the digits 4,1 which can
be halved at least 41 times. The solution is unique !"

Important note:

The description above and below has been duly amended to correct the original wording which erroneously said "precisely 41 times"
where actually it should read "at least 41 times". This was first detected by GE and Marcus von Cube. Thanks a lot for pointing it out and sorry to everyone for any inconveniences.

Of course, "halved N times" means that the number can be halved at least N consecutive
times. For instance, 100 can be halved 2 times: (1) 100/2 = 50, (2) 50/2 = 25, as
25 can't be halved any further to yield an integer result.

Despite its looks it's actually fairly easy, and to prove it I'll give a very short, 7-line
HP-71B program which finds out and outputs the only solution in less than 4 minutes in a physical HP-71B (and less than
a second under Emu71!!).

## Le Dessert: Pi & other delights

A recent HP-15C mini-challenge o'mine featured an infinite, convergent series for Pi/4, namely:
```       Pi/4 = 1 -1/3 +1/5 -1/7 + 1/9 - 1/11 + 1/13 - ...
```
Now this infinite series though convergent, if slowly, is a typical case of what's known as
an alternating series, because its terms steadily alternate between positive and negative.
Furthermore, infinite alternating series like this one, even if convergent, are only conditionally
convergent
, which means that their value depends on the exact order in which its terms are summed up.

So by varying their order, and even though you're still adding up each and every term exactly once and
only once, lo and behold, you can get the series to add up to any arbitrary real value at all,
including Pi/4, zero, negative values, or even make it diverge to infinity !

This understood, "you must write a program which, given an arbitrary value, will output the exact
order in which the terms of this particular series have to be summed up so that the series sums
to precisely that given value".

As all the terms have "1" as numerator, your program needs to
output just the denominators to fully identify each term, in the required order. For instance, assuming you've just written a version for the HP-15C, it should work like
this example (User mode), in which the sum must be precisely Pi/4:

```    Pi/4, [A] ->  1  -> -3  ->  5  ->  -7 ->  9  ->  -11  -> ...
```
where the program can continue indefinitely, if desired, to produce as many terms as the
user cares for. In this example, the output are the denominators, so the order is:
```     Pi/4 =  1/1 -1/3 + 1/5 -1/7 +1/9 -1/11 ...
```
as expected. Use your program with the following cases, outputting a few dozen terms or so:
```     Sum = Pi/4, Pi/5, e/4, Sin(1), Cos(1), 1, 0, 1-1/3+1/5, .71, .41
```
I'll give both my original solutions, namely a 3-line program for the HP-71B and a 30-step version
of it for the HP-15C, both taking negligible time.

That's all. I'll post my original solutions next week, so you've got plenty of time
to work yours out. Now respect the rules, sharpen your ingenuity, post your achievements,
and ... Enjoy !

Best regards from V.

Edited: 18 Sept 2006, 8:52 a.m. after one or more responses were posted

Quote:
Several months have merrily passed by since I posted my previous S&SMC#16 and
now it's as good time as any to post my brand-new Short & Sweet Math Challenge #17:
The Feast!

It's not such a good time - we're all off to HHC2006. You won't hear anything here except the wind whistling through the tumbleweed!!

Hi, Bruce:

Bruce posted:

"It's not such a good time - we're all off to HHC2006."

Gosh, you're right ! I hadn't noticed !! :-( :-(

I'll delete my post immediately so please hold your breath while I'm at it, it'll take just a moment ...

Best regards from V.

Ditto Bruce .... the only pi HHC2006 attendee will have are ones served by San Jose cantinas (aka restaurants).

Namir

I've got an inelegant solution to the first part on the HP49g+:

```    << 512 DO 2 * DUP ->STR 1 4 SUB OBJ-> UNTIL 3 PICK == END >>
```

The output is the power itself rather than the exponent. Runtime for the smallest case beginning 2006... is under a minute. The largest case beginning 1000... takes about three minutes to solve.

I'm guessing that this is faster than attacking the problem mathematically :-)

Converting to get the exponent as asked for is left as an exercise for the reader :-) Either figure it out from the number (beware the limited real exponenet range) or add a counter to the program.

- Pauli

So you cooked some bits for a nice bite, Valentin.

Well, as I'm experienced with powers of 2 (remember? ;-) I made this program as a starter.

```LBL V
STO S	; sequence of digits
LOG
IP
STO D	; number of digits of sequence
0
STO P	; power
1
STO N	; number, 2^P
LBL A
1
STO+ P
2
STO* N
RCL N
ENTER
LOG
RCL D
-
IP
10^x
/
IP
RCL S
x#y?
GTO A
RCL P
STOP
```

Not really brilliant, but it will do, although you'll need something like an HP-32SII because of the very large numbers. Yet only 3 tasks can be computed, the other 2 give an overflow.

1234 XEQ V yields 1545 so 2^1545 starts with 1234

2^1183 starts with 1313

2^682 starts with 2006 (takes 1.5 minutes)

and even 102 XEQ V yields 10 as required

I'll have to run this program in Free42 to get the other two answers. (or find another algorithm)

Now, let's digest the material for a while before continuing ...

My first try at a SSMC, while all were interesting and sometimes mind-bending !!

Challenge 1 :

Apologies for putting a program for a Casio calculator here, that's all I have around today. Here goes :

?->A:log A->B:0->C

Lbl I:C+1->C:Clog 2->D

A=/=Int 10^(B+Frac D)=>Goto I

C

44 bytes plus 32 bytes overhead, and =/= above is the sign 'different from'.

It uses the log(2^N) instead of 2^N to avoid overflows.
This gives 1000=>2136, 1234=>1545, 1313=>1183, 2006=>682, 1776=>2087 in under 30 seconds in all cases.

The theory is to calculate the first few digits of 2^N using the floating point approximation, which should be precise enough for this (not proven here). I wonder if ALL integer values can be found as the beginning sequence of a power of two, my guts feeling being a big NO, but...

Challenge 2.

Only ideas here. Only the leftmost N digits are relevant for the first N halvings, so at each step based on the parity of the current value of X/2^N we can determine the next digit as being 4 or 1, there is one solution and there is only one, we can build it digit by digit.

Note that the two digits must have different parity but could be anything. Note also that a N digits number cannot be halved more than log(N)/log(2) times, so there is also a solution for halving that 41-digit number (less than 10^42) made of two different parity digits exactly P times for P between zero and 139 times (because 42/log2 = 139,52).

Sorry I had not the juice to build the multi-precision program which would spit each digit, maybe later.

Challenge 3.

Ideas only, I'll check before posting here.

And again many thanks to Valentin for these really interesting, fun puzzles.

Brute force and ignorance on part one (exponent only).

```102  => 2^10
1000 => 2^2136
1234 => 2^1545
1313 => 2^1183
2006 => 2^683
1776 => 2^2087
```
And some boundary cases (not absolutely sure about the last two, but they're what these programs give) (I know these go beyond the specs):
```1    => 2^0
9999 => 2^13301
9975 => 2^9999
```

1542 is a somewhat interesting case.

For the HP25 (minor and obvious changes for almost any RPN machine(?)):

```01 STO 1
02 LOG
03 INT
04 STO 2
05 1
06 CHS
07 STO 3
08 2
09 LOG
10 STO 4
11 1
12 STO + 3
13 RCL 3
14 RCL 4
15 *
16 ENTER
17 FRAC
18 x<>y
19 INT
20 RCL 2
21 x<y?
22 x<>y
23 Rdown
24 +
25 10^x
26 EEX
27 CHS
28 4
29 +
30 INT
31 RCL 1
32 x#y?
33 GTO 11
34 RCL 3
```

HP-48GX (and most RPL machines(?)):

```<<
DUP LOG IP -1 2 LOG -> n g i t
<<
DO
UNTIL t 'i' INCR * DUP FP SWAP IP g MIN
+ ALOG 6 RND IP n ==
END
i
>>
>>
```

HP-71B:

```10 INPUT N @ L=IP(LOG10(N)) @ I=-1 @ T=LOG10(2)
20 I=I+1 @ P=I*T @ Q=FP(P)+MIN(IP(P),L) @ P=IP(10^Q+.0001) @ IF P#N THEN 20 ELSE PRINT I
```

Edited: 14 Sept 2006, 7:11 p.m.

The third challenge.

I'm aware of the approch mentioned in this paper (PDF file). I'm reasonably confident that something similar could be done in this case.

Since following that path would be no fun, I present a *twenty-one* step HP-12c program that achieves the goal in a different manner:

```    01  STO 0
02  1
03  STO 1
04  STO 2
05  STO 3
06  PSE             Display the first 1 term
07* RCL 0           Main loop
08  RCL 3           Compare current total
09  x<=y?             against target number
10  GTO 18
11  4               Above target
12  STO- 2          Add next negative term
13  RCL 2
14* PSE             Display the term
15  1/x             And add it into our sum
16  STO+ 3
17  GTO 07
18* 4               Below target
19  STO+ 1          Add next positive term
20  RCL 1
21  GTO 14
```

The basic premesis is that if the running sum is greater than the target, we add a negative term and if it is less, we add a positive one. I think a proof of convergence should be fairly straightforward but I'll leave that (or proof that this is wrong) as an exercise...

- Pauli

Edited: 14 Sept 2006, 8:46 p.m.

Hello, some more news :

Challenge 1 :

-------------

Dug out an HP28S and typed the following program which gives the same results. It is the simplest I can do, achieved as usual by avoiding stack monkey business and the ugly STO syntax. This program also shows how far we've gone since HP28 days, as that machine is very significantly slower than the Casio... A wonderful calculator IMHO despite RPL. Note that internal precision allows for no rounding and still correct results !

<< DUP LOG IP -> A B << 0 DO 1 + UNTIL

DUP 2 LOG * FP B + ALOG IP A == END >> >>

Challenge 2 :

-------------

As stated a direct approach is possible and gives the following program on the Casio. This version is in single precision, and thus works only up to 9 digits.

8->B:{4,1}->List 1

0->N:0->M

For 0->D To B-1

List 1[1+2Frac (N+2)]->A

(N+A*5^D)/2->N

M+A*10^D->M:Next

List 1[2-2Frac (N+2)]->A

M+A*10^(D+1)->M:M

I extended it in a 'brute force' way to multi precision and that gave an horrible 600 bytes program that I will NOT write down here, this program finds the solution but per the rules I will not show the solution only (it begins with 111111...).

Just for fun here is the 67-digit number containing only digits 6 and 7 which is exactly 67 times halvable :

76767767767776677666776766676776777676767667777666766777666766667776, found in about 10 seconds on the Casio 85 (the currently fastest Casio). You just have to change the parameters in the first line, here as :

67->B:{6,7}->List 1

Challenge 3 :

-------------

Same idea as Dale, congratulations.

Note that a divergent series remains divergent if you remove a finite number of terms, this suffice to validate the procedure.

Waiting for SSMC 18 !!

Hi, GE:

GE boldly posted:

"Just for fun here is the 67-digit number containing only digits 6 and 7 which is exactly 67 times halvable :
76767767767776677666776766676776777676767667777666766777666766667776, found in about 10 seconds on the Casio 85"

Very funny, indeed, but either your Casio isn't working as it should, or your programming is slightly faulty, or you missed school the day counting was taught ! :-) :-) Because your "67-digit number", as posted by you, is actually a 68-digit number, and further, it isn't 67 times halvable but only 15.

I can't comment on your 41-digit result or your multi-precision program capable of computing it as you provided neither. Perhaps a little rechecking is in order ? :-) All in good humor, of course, no offence whatsoever intended :-) :-).

"Waiting for SSMC 18 !!"

Seems to me that you've still some work to do with the "main course" before asking for S&SMC #18. Unfinished business :-)

Best regards from V.

Edited: 15 Sept 2006, 6:10 a.m.

This is just another RPN version to the first challenge, but I think it may be faster than others posted earlier.

I have tried it on the 42S, but it's very easily adaptable to other models.

```01 LBL AB
02 1
03 STO 00
04 STO -00
05 LBL 01
06 1
07 STO +00
08 Rdown
09 ENTER
10 +
11 IP
12 X=Y?
13 GTO 00
14 Rdown
15 LASTX
16 X<Y?
17 GTO 01
18 0.1
19 *
20 GTO 01
21 LBL 00
22 RCL 00
23 END
```

Now it's time to try to tackle the other two challenges.

Thanks, Valentin, for keeping us entertained over the weekend !

Best regards from V.

Aaargh, you are right !!!!!! Time to search for my PI button...

"I'll be back", showing the program after some much-needed debugging.

And no offence taken, that doesn't fit here.

Hi Valentin,

Here is an RPL solution to the main course: Le petit homage to the 41! I didn't read any of the other postings before in order not to get spoiled by someone elses genius ;-)

I did it on my new 50g in exact mode because it can easily cope with 41 digit integers.

But first a little theory how it works:

If you want to decide whether a number is divisible by 2, just check the last digit: If it is divisible by 2, the whole number is.

If you want to decide whether a number is divisible by 4, just check the last two digits: If they (as a number) are divisible by 4, the whole number is.

More general: If you want to decide whether a number is divisible by 2n, just check the last n digits: If they (as a number) are divisible by 2n, tho whole number is.

Now I start building the number from back to front. Since the digits can only be 1 or 4, the goal is to prepend one of these to the result found so far and check for divisibility by the proper power of 2. The result is unique because exactly one of the digits one or four yields to a number which is evenly divisible (the difference between the two possible results is 3*10n-1 which is not divisible by 2n.)

To ease the algorithm, the program starts with n=2 and result=4. It takes the number of places (and hence the power of 2) from the stack. Minimum input is 2, smaller numbers are treated as 2.

Here is the code:

```%%HP: T(3)A(R)F(.);
\<<
1 2 4 \-> n f d r
\<<
2 n START
10 'f' STO*
2 'd' STO*
f r +      @ First try with digit 1
DUP d MOD
IF 0 \=/ THEN
f 3 * +  @ Digit must be 4
END
'r' STO
NEXT
r            @ result goes to stack
\>>
\>>
```

The result for 41 is:

```44111111411444111411141441444411441414144
```

The computing time is within seconds.

[Edited: The given result is not exactly but at least n times halvable. Valentin is about to correct his original posting to match this request.]

Marcus

Edited: 18 Sept 2006, 4:34 p.m. after one or more responses were posted

Problem 3 seems to be the easiest.

The principle here is just to add a term if the sum is less than the desired value, subtract if it's greater, and go to the next term (whichever the case may be) if they're equal.

You put the desired value on the stack, and select "okay" from the choose boxes as long as you want more terms. Selecting "cancel" will end the program, with the desired value on level 2, and the approximation using the sum, for comparison, on level 1.

```
%%HP: T(3)A(R)F(.);
\<< 0. 0. 0. \-> V P N S
\<< 1.
DO DROP V S >
IF
THEN P 4. * 1. + DUP INV S + 'S' STO P 1. + 'P' STO
ELSE V S <
IF
THEN N 4. * 3. + NEG DUP INV S + 'S' STO N 1. + 'N' STO
ELSE V S ==
IF
THEN P N \<=
IF
THEN P 4. * 1. + DUP INV S + 'S' STO P 1. + 'P' STO
ELSE N 4. * 3. + NEG DUP INV S + 'S' STO N 1. + 'N' STO
END
END
END
END \->STR DUP "{{" SWAP "}}" + + OBJ\-> 1. CHOOSE
UNTIL NOT
END V S
\>>
\>>
```

The first few terms in the sequences for various desired values:

```
pi/4
1, -3, 5, -7, 9, -11, 13, -15, 17, -19, 21, -23
pi/5
1, -3, -7, 5, -11, -15, 9, -19, 13, -23, -27, 17
e/4
1, -3, 5, -7, -11, -15, 13, -19, -23, 17, -27, -31
Sin(1)
1, -3, 5, -7, 9, 13, -11,  17, -15, 21, -19, 25
Cos(1)
1, -3, -7, 5, -11, -15, -19, 9, -23, -27, -31, 13
1
1, -3, 5, 9, 13, -7, 17, 21, -11, 25, 29, -15,  33
0
1, -3, -7, -11, -15, -19, -23, -27, -31, -35, -39,
-43, -47, -51, -55, -59, -63, -67,  -71, -75, 5
1-1/3+1/5
1, -3, 5, -7, 9, 13, -11, 17, -15, 21, 25, -19
.71
1, -3, 5, -7, -11, 9, -15, 13, -19, 17, -23,  -27, 21
.41
1, -3, -7, -11, -15, 5, -19, -23, -27, -31, 9, -35
```

Edited: 15 Sept 2006, 2:58 p.m.

Quote:
Challenge 3 :

-------------

Same idea as Dale, congratulations.

Valentin's HP-15C program is some thirty steps which is quite a bit longer than my HP-12C progam (twenty one) or a naive conversion of this to the HP-15C (twenty four). Even skipping the hard coded initial '1' term doesn't bloat the program enough. I wouldn't be at all surprised if Valentin is attacking this problem differently.

- Pauli

Here is my attempt at the appetizer.

It's another RPL program but the logic should be portable to almost any programming language. The algorithm does not test all powers of 2 against the given number x but it computes the matching exponent r of two directly (r = "result"):

```r := CEIL( log2( x * 10n ) )
```
It then checks, if
```         2r
x == IP( --- )
10n
```
n is a shift factor that is increased in a loop until a match is found.

In fact, all formulas are converted to logarithmic form. This avoids large numbers:

```r := CEIL( log2x + n * log210 )
x == IP( 2r - n * log210 )
log210 is a precomputed constant.
```
On the 50g, extended precision integer arithmetic allows to display the exact power of two together with the final result.

The results are exactly the same as already posted by Kiyoshi Akima. And I must agree that 1542 is an interesting case :-)

Here is the code:

```%%HP: T(3)A(R)F(.);
\<<
\->NUM DUP LN 2. LN /
10. LN 2. LN /
0. 0.
\-> x l2x l2t n r           @ l2x and l2t are precomputed logarithms
\<<
WHILE r 2500. <
REPEAT
l2t n *                 @ logarithm of shift factor
DUP l2x + CEIL 'r' STO  @ compute exponent of two
r SWAP - 2. SWAP ^ IP   @ 2nd formula from above
IF x ==
THEN
r \->Q DUP 2 SWAP ^   @ format result
1.E99 'r' STO         @ make loop terminate
ELSE
'n' INCR DROP         @ try next power of ten
END
END
\>>
\>>
```

Running times are about 20 seconds for the greater results.

Marcus

Hi, Paul:

Paul posted:

"Valentin's HP-15C program is some thirty steps which is quite a bit longer than my HP-12C progam (twenty one) [...] I wouldn't be at all surprised if Valentin is attacking this problem differently."

No, that's not it. It's simply that my HP-15C program is a rough translation of my original 3-line HP-71B BASIC program, without further thoughts or optimizations, and the HP-71B solution itself is also pretty straightforward, the first thing that came to mind. Neither are brilliant pieces of code, after all it's just the "dessert" ! :-)

Best regards from V.

Although not for a calculator, here is the same algorithm written in C:

```#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// Compile using: gcc -o x x.c -lm -std=c99 -O
int main(int argc, char *argv[]) {
unsigned int x = atoi(argv?:"0");
int n;
if (x == 0)
return 1;
long double log2_10 = log2l(10);
long double log2_x = log2l(x);
long double r = 0;
for (n=0; r<1000000; n++) {
// long double n10 = powl(10.0, n);
long double nlog2_10 = n * log2_10;
r = ceill(log2_x + nlog2_10);
long double t = truncl(powl(2, r - nlog2_10));
if (x == t) {
printf("%Lg\n", r);
return 0;
}
}
printf("failed to locate solution\n");
return 0;
}
```

Run time is rather small :-)

Using this, I've verified that all five digit or fewer leading sequences can be found. For each length, here is a table of the last sequence to be found and the power of two where it occurs.

```    len    digit(s)   power
1         9      2^53
2        97      2^279
3       982      2^3973
4      7629      2^28721
5     95367      2^325127
```

There might be some merit to the earlier suggestion that any integer could be found in the leading digits of a power of two.

- Pauli

Hello again.

I killed the 3 bugs in my program but (as you noted) what I have found is a way to very quickly find N+1-digits numbers which are N-halvable (and containing only two digits which are different modulo 2).

This can be modified easily to give N-digit numbers which are *AT LEAST* N-halvable, but this method doesn't guarantee it is not N+1-halvable (or more).

And in the case of 41, alas, the 41-digit number I get is 42-halvable, so (per the rules) I doesn't solve the problem and I can publish it : 44111111411444111411141441444411441414144.

Just for fun here is a correct 65-digit, 65-halvable number made of only the digits 6 and 5 (calculation time about 15 seconds) :

66656565566565655566565665666666566656655655556556566656666566656

This also works for the "HP-numbers" 12, 21, 25, 32, 34, 45, 49, 81 and 85.

Since you said that there is a solution for the 41 case, I have not tried to prove that this number doesn't exist... enough made a fool of myself... and writing a brute force program (testing the 2^41 possibilities) doesn't taste good. Out of theoretical ideas for now, I leave it to others to find the shortcut.

Sorry Marcus, this number is 42-halvable...

I am currently trying to understand why a 41-halvable number could possibly **exist** at all, so I'm waiting for :

- Valentin to publish his number OR

- my brain to start working

whichever comes first... and you can guess which will come first !!

By the way, this SSMC is great.

Hi GE,

I should have checked my own solution better! The number my program gave is exactly the one you posted here and it is 42 time halvable.

:-(

Back to the drawing board!

Marcus

GE,

our postings crossed eachother, I've just found it out! I have to go back to my ideas.

Marcus

The problem with my "solution" is that the last digit is a 4 and hence divisible by 22. Now following the algorithm, I always get numbers which are divisible by another power of two. The result is that all numbers my program produces are divisible by 2n+1 where n is the number of digits.

Does this mean, there is no solution or is my algorithm wrong?

Marcus

Hi, Marcus & GE:

Marcus posted:

"I should have checked my own solution better! The number my program gave is exactly the one you posted here and it is 42 time halvable."

No, the error's actually mine, I said "precisely 41 times" where I should have stated "at least 41 times", because as both of you correctly pointed out, the solution number is indeed divisible by 2 more than 41 times.

Matter of fact, there would be no solution if the number had to be divisible by 2 exactly 41 times, as there's but a single choice for the digit, 4 or 1, at each step. If putting a 4 makes the number divisible 42 times, putting a 1 instead would make it divisible just 40 times, and there are no other possibilities.

Sorry for the inexact wording, I'll correct my original posting when the thread's finished for good, so that it doesn't get archived with the error in place, with an explanation for the need of the correction and full credit to you.

Thanks and best regards from V.

Best regards from V.

Best regards from V.

Valentin,

I've edited my posting again to refer to your correction.

Marcus

> The problem with my "solution" is that the last digit is a 4

> and hence divisible by 22.

Yuckkkk !!! NOT ALL (hum) numbers ending in 4 are divisible by 4.

Actually, EVERY N-digit number divisible by 2^N containing only digits 4 and 1 and whose first digit is 1 is divisible by NO MORE than 2^N.

Those beginning with 4 are divisible by 2^(N+1).

Hopefully my mother has no Internet access.

Hi, GE:

GE boldly posted:

"Actually, EVERY N-digit number divisible by 2^N containing only digits 4 and 1 and whose first digit is 1 is divisible by NO MORE than 2^N."

Nope. For instance, 144 is a 3-digit number divisible by 2^3 (8), containing only digits 4 and 1, and whose first digit is 1.

Yet it is divisible by 2^(3+1), as 144 = 16 * 9.

"Hopefully my mother has no Internet access."

Let's hope ... ;-)

Best regards from V.

Hi all,

Thanks once more for your interest and for the excellent inputs and kind comments,
much appreciated. I must say that it's becoming increasingly difficult to come up
with a worthy challenge capable of resisting your combined efforts even for
a few days. I dread the day when my S&SMCs will be completely solved within a few
hours after posting ! This only goes to show the tremendous amount of programming
& math ingenuity displayed by this forum's gentle contributors.

That said, these are my original solutions to all three parts of S&SMC#17, plus

Appetizer: More power to you

"Write a program to find the first exact power of 2 (up to 22500, say) that begins by a given
sequence of up to four digits"

First of all, it's fairly simple to prove that for any positive integer M there exists
an exact power of 2 that begins with the sequence of digits which represents the number M in the
decimal notation. Which is more, this is also true not only for 2 but for any positive integer A
other than an exact power of 10, so for example, you can find N such that
3141592654N begins with 2718281828, say.

Once we know that the feat is indeed possible for any given M, we can proceed to implement the
search, and this 3-liner (97 bytes) is my original solution for the HP-71B:

```    1 INPUT M @ X=FP(LGT(M)) @ Y=FP(LGT(M+1)) @ P=LGT(2) @ FOR I=1 TO 2500
2 N=FP(P*I) @ IF N>X AND N<Y THEN DISP I,STR\$(10^N);"E";STR\$(INT(P*I)) @ END
3 NEXT I
```
which will accept an integer M, then will find out and print the required exponent and
the corresponding power of 2 (which begins with M) in exponential notation, using decimal logarithms
throughout to keep the numbers within range. Upon running it for the given cases, we construct
the following table:
```    Beginning    N       2^N
-----------------------------------------
1000         2136    1.00016289353E643
1234         1545    1.23407996301E465
1313         1183    1.31366573155E356
2006          682    2.00658260481E205
1776         2087    1.77664619863E628
```
and we also try out Kiyoshi Akima's suggestion:
```    1542         1542    1.54259995373E464
```
which is indeed rather nice, as the required exponent equals the given beginning sequence,
namely 1542, so that we have:
```    21542 = 1542.59995373 * 10461
```
For the longer case, outputting the resulting power of 2 in full, it suffices to append
a routine to compute the exact value of 2N using some multiprecision algorithm. I'll simply
use the one I already posted as part of my "Spring Special Challenge" (aka "April's Fool Challenge"), where it was
used to efficiently compute 265536-3, and which is readily customizable
for an arbitrary power of 2. The resulting program is thus the following 426-byte quick concoction:
```    10 DESTROY ALL @ OPTION BASE 0 @ INPUT M
15 X=FP(LGT(M)) @ Y=FP(LGT(M+1)) @ P=LGT(2)
20 FOR I=1 TO 2500 @ N=FP(P*I) @ IF N>X AND N<Y THEN 30
30 N=I @ PRINT N @ M=9 @ DIM A(1) @ K=10^M
35 A(0)=1 @ P=0 @ L=9 @ R=2^L @ FOR J=0 TO N-L STEP L @ MAT A=(R)*A @ GOSUB 65
40 IF NOT MOD(J,27) THEN DIM A(UBND(A,1)+1)
45 NEXT J @ R=MOD(N,L) @ IF R THEN MAT A=(2^R)*A @ GOSUB 65
50 J=0 @ PRINT @ PRINT STR\$(A(P));
55 FOR I=P-1 TO 0 STEP -1 @ J=J+1 @ IF J=7 THEN PRINT @ J=0
60 A\$=STR\$(A(I)) @ PRINT RPT\$("0",M-LEN(A\$));A\$; @ NEXT I @ END
65 FOR I=0 TO P @ A(I+1)=A(I+1)+A(I) DIV K @ A(I)=MOD(A(I),K) @ NEXT I
70 P=P+SGN(A(P+1)) @ RETURN
```
Let's try a couple of cases:
```    >RUN
? 2006
682
20065826040452474621738395244141115820123061381619162977212070
095324448220432589806036630768881181530864650607514107580997541
169167266097500334986765487216377087492641938951866881041556870
737904629872328704
```
which takes just 0.43 seconds in Emu71 (some 2 min. in an actual HP-71B).
Another interesting case is Kiyoshi Akima's 1542:
```    >RUN
? 1542
1542
154259995322946085669127462785812103226373967868524092887019
202500176473061875404842821441542870147178460721041976832306423
194686642877332798055231225009577693133653720424014385330052986
731615979318114760792820483686230134905894343005528775814368509
759860201045907243368286294738023515418354826493938295703703614
022990181884355470848740016540805157093622457663597753106142505
384395616964083511896011664672399807541625517182144801653972761
678911158848304661716271104
```
which takes only 1.64 seconds in Emu71 and some 8 min. in a real HP-71B.

Main course: Le petit homage to the 41 !

"Find a 41-digit number consisting solely of the digits 4,1 which can
be halved at least 41 times"
.

As stated, this is actually quite easy, because you can begin with just one digit (4), which is certainly
divisible by 21 and go on adding digits leftwards one at a time, chosing 1 or 4
so that the resulting number is divisible by 22, 23, etc.
This is almost trivial up to 10-12 digits (depending on your chosen calc model), for instance this
would be one of the simplest HP-71B implementations, valid for up to 12 digits:
```    1 DESTROY ALL @ U=4 @ V=1 @ N=U @ P=4 @ T=10
2 FOR K=2 TO 12 @ IF MOD(N,P) THEN N=N+T*V ELSE N=N+T*U
3 DISP K;N @ P=P*2 @ T=T*10 @ NEXT K
>RUN
2  44            (divisible by 22,  "14" wouldn't be)
3  144           (divisible by 23, "444" wouldn't be)
4  4144
5  14144
6  414144
7  1414144
8  41414144
9  441414144
10  1441414144
11  11441414144
12  411441414144  (divisible by 212)
```

and afterwards, for more than 12 digits, you only need a multiprecision modulus operator,
which is rather easy to implement as can be seen in my following original 7-line solution for
the HP-71B, which is general because it will work not only for the (4,1) case but for all other
solvable cases as well, namely all pairs of digits which are of different parity (i.e.: one odd, the other even,
zero not included):

```    1 DESTROY ALL @ INPUT U,V @ D=U+1 @ DIM N(D),B(D) @ N(1)=U @ L=10^11
2 FOR K=2 TO 10*U+V @ W=1 @ MAT B=N @ FOR J=1 TO K @ FOR I=D TO 1 STEP -1
3 IF NOT MOD(B(I),2) THEN 4 ELSE IF I#1 THEN B(I-1)=B(I-1)+L ELSE 5
4 B(I)=B(I) DIV 2 @ NEXT I @ NEXT J @ W=0
5 C=(K-1) DIV 11+1 @ N(C)=N(C)+(V*W+U*NOT W)*10^MOD(K-1,11) @ NEXT K
6 DIM T\$[11*D] @ FOR I=1 TO D @ S\$=STR\$(N(I))
7 T\$=RPT\$("0",11-LEN(S\$))&S\$&T\$ @ NEXT I @ DISP LTRIM\$(T\$,"0")
```
Running it for all 20 possible cases, you'll get the following table:
```   Digits  Number
--------------------------------------------------------------------------------------------------
2,1    112111211111212122112
2,3    23233333323323232223232
2,5    5255552222255222255255552
2,7    727727727272277772727222272
2,9    29229292922999929922222292992
4,1    44111111411444111411141441444411441414144
4,3    4334333333433343344344443443433343333433344
4,5    554445454544445545455455454544555545454444544
4,7    74744444477474477447474474777477444474444447744
4,9    4944949944994494999944449444499949499449494994944
6,1    1116116116116166111166666166166666666111616666661661616111616
6,3    663336366333366636336636363336363363366333336333633333636366336
6,5    66656565566565655566565665666666566656655655556556566656666566656
6,7    6677767667676666776766667777767666677766776777777777777666766667776
6,9    969669666696696696696996666999996996999999996669699999969969696669696
8,1    888811111811181118188118188188811181881818811811881181181818888181888888118181888
8,3    88333833333888383338883833838333388383333888883833338883388388888888888833383333888
8,5    5858588588585858858858558558588888588855588858585588588555858555888855585858558885888
8,7    878788788878877877788787778887877888877787887787878887878878877888887888788888787877888
8,9    99999989998899889889988898999988888898989889899889988989999888898888999898998898989989888
```
The solution for the (4,1) case is thus this 41-digit number, obtained after 4 min. in a
physical HP-71B (less than 1 second in Emu71):
```    44111111411444111411141441444411441414144
```
which indeed is the only 41-digit long number consisting solely of the digits (4,1), and which can be halved
at least 41 consecutive times (actually, 42!). Also, the correct solution for the digits (6,7) is:
```    6677767667676666776766667777767666677766776777777777777666766667776
```
which is 67-digits long, consisting of just the digits (6,7), and
can be halved at least 67 consecutive times. Running time is 15 min. in a real HP-71B (less than 4 seconds in Emu71).

By the way, before departing let's have a look at these nice 'cousins' of our number which I've generated for your viewing pleasure, also 41-digit long
and consisting solely of the digits (4,1):

```    44144444111441144114411411444444411441441 =  12009881291601907477 * 3675676972953081511133 (both prime)
41411111444114444411114141144414144444441 =  is a prime
```
and these are two equally handsome 'cousins' I've generated for the 67-digit (6,7) number:
```    6777766776766667676667667777777667667776766667766766666767676677677
= 17512766212863416348551 * 387018629403519697077017550365961771489126827 (both prime)
6677776776776667776677667776667677766767676666766666766676767677677 = is a prime
```
Who knows, they might come handy to test your favorite factoring or primality test algorithms, or even
your multiprecision multiplication routines at the very least. Or, if you're in a little sadistic mood and
you've got some students the right age, have them multiply both factors by hand and keep betting whether
the next digit in the result is going to be a 6 or a 7 ! ... :-)

Le Dessert: Pi & other delights

"Write a program which, given an arbitrary value, will output the exact
order in which the terms of this particular series have to be summed up so that the series sums
to precisely that given value"

This is probably the easiest of the lot, and this 4-liner (147 bytes) is my original solution
for the HP-71B, which is anything but optimized (pessimized more like!) and will output up to
100 terms, then it will display both the given value and the sum after 100 terms:
```    1 DESTROY ALL @ INPUT E @ K=100 @ P=1 @ N=2 @ S=0 @ FOR I=1 TO K
2 T=2*P-1 @ S=S+1/T @ DISP T; @ P=P+2 @ IF S<E THEN 2
3 T=1-2*N @ S=S+1/T @ DISP T; @ N=N+2 @ IF S>E THEN 3
4 NEXT I @ DISP @ DISP E,S
```
Let's run it for a few cases:
```
>RUN
? PI/4
1 -3  5 -7  9 -11  13 -15  17 -19  21 -23  25 -27  29 -31  33 -35  37 -39  41 -43  45 -47  49
-51  53 -55  57 -59  61 -63  65 -67  69 -71  73 -75  77 -79  81 -83  85 -87  89 -91  93 -95  97 ...
.785398163398        .784148171212
>RUN
? PI/5
1 -3 -7  5 -11 -15  9 -19  13 -23 -27  17 -31 -35  21 -39 -43  25 -47 -51  29 -55 -59  33 -63
-67  37 -71 -75  41 -79  45 -83 -87  49 -91 -95  53 -99 -103  57 -107 -111  61 -115 -119  65 ...
.628318530718        .627954521532
>RUN
? EXP(1)/4
1 -3  5 -7 -11  9 -15  13 -19 -23  17 -27 -31  21 -35  25 -39 -43  29 -47  33 -51 -55  37 -59
41 -63 -67  45 -71  49 -75 -79  53 -83  57 -87 -91  61 -95  65 -99 -103  69 -107  73 -111 -115 ...
.679570457115        .678047886984
>RUN
? 1
1 -3  5  9  13 -7  17  21 -11  25  29 -15  33  37  41 -19  45  49 -23  53  57 61 -27  65  69
-31  73  77 -35  81  85  89 -39  93  97 -43  101  105 -47  109  113  117 -51  121  125 -55  129 ...
1                    .998110828956
>RUN
? SIN(1)
1 -3  5 -7  9  13 -11  17 -15  21 -19  25 -23  29  33 -27  37 -31  41 -35  45 -39  49  53 -43
57 -47  61 -51  65 -55  69  73 -59  77 -63  81 -67  85 -71  89  93 -75  97 -79 101 -83  105 ...
.841470984808        .840058963385
>RUN
? COS(1)
1 -3 -7  5 -11 -15 -19  9 -23 -27 -31  13 -35 -39  17 -43 -47 -51  21 -55 -59 -63  25 -67 -71
29 -75 -79 -83  33 -87 -91 -95  37 -99 -103  41 -107 -111 -115  45 -119 -123 -127  49 -131 ...
.540302305868        .539956898016
>RUN
? 0
1 -3 -7 -11 -15 -19 -23 -27 -31 -35 -39 -43 -47 -51 -55 -59 -63 -67 -71 -75  5 -79 -83 -87 -91
-95 -99 -103 -107 -111 -115 -119 -123 -127 -131 -135 -139 -143 -147 -151 -155 -159 -163  9 -167 ...
0                   -1.03546604552E-4
```
I think you get the idea: though we're adding up each and every term of the series
once and only once, we can get any result we want by simply
chosing their order
in
the addition process, which is probably rather unexpected at first sight and nicely shows what
conditional convergence of alternating series actually means.

As for the 30-step HP-15C version, it was a direct translation of the
above 71B program and it doesn't bear being featured here as much better and shorter solutions
have already been provided by you.

That's all. I hope you enjoyed it all and, again, thanks for your interest and stay tuned for
S&SMC#18 coming next month.

Best regards from V.

Edited: 19 Sept 2006, 5:52 a.m.

Thank you again Valentin, this SSMC was very interesting. I can't wait to see the next, it must actually be difficult to find interesting subjects.

 Possibly Related Threads... Thread Author Replies Views Last Post Need help understanding math.... cyrille de Brébisson 9 2,409 12-13-2013, 02:23 AM Last Post: Didier Lachieze HP Prime - Short "learning" modules CR Haeger 1 971 11-27-2013, 02:13 PM Last Post: Jonathan Cameron I have written a short introduction to the HP Prime Michael Carey 7 2,023 11-18-2013, 08:04 PM Last Post: Michael Carey HP-65 short circuit Ignacio Sánchez 2 1,102 10-22-2013, 08:27 AM Last Post: Ignacio Sánchez Reig OT: a math competition site Pier Aiello 0 764 09-16-2013, 06:03 AM Last Post: Pier Aiello Simple Math Question Namir 2 1,015 08-09-2013, 06:13 PM Last Post: Eddie W. Shore Update of Emu42 to v1.17 Christoph Giesselink 1 816 05-15-2013, 09:30 AM Last Post: CompSystems Cool math clock Bruce Bergman 28 5,144 04-10-2013, 03:13 AM Last Post: Siegfried (Austria) NCTM, Denver April 17-20 Tim Wessman 1 729 03-16-2013, 06:41 AM Last Post: bluesun08 FRAM71 for HP-71B, short update #3 Hans Brueggemann 15 2,789 01-20-2013, 10:22 AM Last Post: Jerry Raia

Forum Jump: 