35s/42S mini challenge « Next Oldest | Next Newest »

Write in 9 steps or less of logic (LBL/RTN not counted) a program that can identify if a positive integer can be represented as 2j-2k where j>=k>=0. If so return a 0, if not return > 0. There is no need to identify j and k.

NOTE: No EQN to keep it 42S friendly.

I've got an almost solution in 9 steps, 6 if I'm allowed to keeps a constant in a register (enter the code at step 4 in this case):

```1: 1
2: STO 00
3: X<>Y
4: RCL- 00
5: LASTx
6: OR
7: RCL+ 00
8: LASTx
9: AND
```

This is for the 42s. For the 35s, replace register 00 with A.

[edit: ignore this next paragraph, I erred]

The reason I said almost is that this routine returns zero for inputs of (2^n)-1 where it should return non-zero. In essence, this code is identifying the presence of a single block of binary 1's in the number rather than a single block of binary 1's with at least one lower order 0 digit.

- Pauli

[edit: clarified the 2^n-1 in the exception]

Edited: 20 Sept 2007, 6:39 p.m. after one or more responses were posted

Similar to my solution, but mine is exactly the same 9 steps for the 35s, 42S, and the 16C and it returns 0 for 2j-1 (i.e. k=0).

Edited: 20 Sept 2007, 6:30 p.m.

My mistake, the routine should return 0 for the (2^n)-1 case and my code does this. Don't know what I was thinking thinking it should return non-zero here :-(

- Pauli

But I get down to six if I can keep the constant 1 in a register ahead of time.

I'd be surprised if the 16c couldn't do this in less steps or at least in a more interesting way...

- Pauli

Got one for the 16c:

```1: LJ
2: X<>Y
3: LBL 0
4: SL
5: F? 4
6: GT0 0
```

Shorter and mostly slower :-)
Well shorter if I don't get my pre-filled register. Only more instructions executed for cases with more than 2 sequential bits set.

- Pauli

Edited: 20 Sept 2007, 6:49 p.m.

I tried the "divide by two, finite state machine" approach:

```A001  LBL A
A002  STO A
A003  0
A004  RCL A
A005  IP
A006  2
A007  <divide>
A008  STO A
A009  FP
A010  x=y?
A011  GTO  A004
A012  X>0?
A013  GTO  A004
A014  RCL A
A015  RTN
```

(Obviously, I miss the target # of steps.)

It initializes its state (in the Y register) to zero and then starts shifting bits to the right. As long as the bit shifted into the fractional portion is a zero, it continues.
When the first non-zero bit is encountered, line A013 leaves it for the new state and continues shifting right.
The first zero bit encountered after encountering any non-zero bits causes the test at A012 to fail, and the last value stored is the result.

(It falls into an endless loop with a zero input, but the problem specifically states "a positive integer".)

I suspect there may be a way to trim it down by skipping the storage register (A) and using LASTx carefully, but I don't have the time right now.

Edited: 20 Sept 2007, 7:27 p.m.

Here's a stack-only version:

```S001  LBL S
S002  XEQ S013
S003  XEQ S009
S004  x<>y?
S005  x>0?
S006  GTO S003
S007  LASTx
S008  RTN
S009  LASTx
S010  IP
S011  2
S012  <divide>
S013  FP
S014  RTN
```

Same logic as before. The comparison test trick on lines S004 & 5 could be used to reduce the previous version by 1 instruction.

If I may assume 0 in y, then the following requires only 10 steps of logic:

```S001  LBL S
S002  GTO S007
S003  LASTx
S004  IP
S005  2
S006  <divide>
S007  FP
S008  x<>y?
S009  x>0?
S010  GTO S003
S011  LASTx
S012  RTN
```

If I further require the user to enter "XEQ S006" to initiate the program, I can get rid of S002 and get down to the target of 9. (I suspect that won't work for the 42s, though.)

Edited: 21 Sept 2007, 2:04 p.m.

Quote:
...get down to the target of 9.

That would be impressive; a non-bitwise operator solution in 9 steps.

Thanks.

Thanks to you for the challenge!

And, just to spell it out:

```S001  LBL S
S002  LASTx
S003  IP
S004  2
S005  <divide>
S006  FP
S007  x<>y?
S008  x>0?
S009  GTO S002
S010  LASTx
S011  RTN
```

Enter 0 in y, the integer in question in x, and then XEQ S006.

Edited: 21 Sept 2007, 5:10 p.m.

My contribution wins the longest listing award!!

The theory behind my program is based on finding j and k for X = 2^j - 2^k):

```X = 2^j - 2^k
X + 2^k = 2^j
log(X + 2^k) = j log(2)
log(X + 2^k) / log(2) = j
```

When the calculated value of j has a zero fractional part we find an answer. The program loops for the values of k, starting with 0 (2^0 = 1 as the initial value of 2^k). If at the end of the loop we find that 2^k > 2^j then we stop the iteration, because it means that k > j which violates one of the requirements for the solution.

The listing is:

```
A001 LBL A
A002 STO X
A003 1
A004 STO K
A005 RCL X
A006 RCL K
A007 +
A008 LOG
A009 2
A010 STO* K
A011 LOG
A012 /
A013 RND
A014 FP
A015 x=0?
A016 STOP
A017 LASTx
A018 2
A019 y^x
A020 RCL K
A021 x<=y?
A022 GTO A005
A023 RTN
```

I inserted the RND because dividing log values sometimes lead to .9999999999 fractions. Also note that register K stores the value of 2^k.

The above approach (and program) can easily be adapted for integers other than 2.

Edited: 21 Sept 2007, 12:22 p.m.

Quote:
My contribution wins the longest listing award!!

Long, but portable. Thanks for providing a non-bitwise solution. I had hoped for one or two like this.

Thank you all for participating in this mini challenge. I selected this challenge because there was more than one way to do it. The most economical way was to use the bitwise operators in the LOGIC menu of the 35s/42S. (I left a hint to consider using logic.)

Paul Dale did come up with a logical 9 step solution. Congratulations Paul!

## Part 1 Problem

Write in 9 steps or less of logic (LBL/RTN not counted) a program that can identify if a positive integer can be represented as 2j-2k where j>=k>=0. If so return a 0, if not return > 0. There is no need to identify j and k.

## Part 1 Solution

My solution is similar to Paul's and will work unmodified on the 35s, 42S, 16C, and possibility other models with bitwise operators. I have been unable to get it down to less than 9 steps.

```ENTER
ENTER
ENTER
1
-
OR
1
+
AND
```

Below is a play-by-play to explain how this works.

Consider the expression 225-217 = 33423360.

```      225 = 00000010000000000000000000000000 = 33554432
217 = 00000000000000100000000000000000 =   131072
225 - 217 = 00000001111111100000000000000000 = 33423360
```
As Paul pointed out it this problem is about identifying an single contiguous block of 1s. 2j - 2k will always be a single block of bits with the range 2k to 2j-1.

Let x = 225-217,

First subtract 1 from x then OR it with x. This replaces all right trailing zeros with 1s:

```                      x = 00000001111111100000000000000000 = 33423360
x - 1 = 00000001111111011111111111111111 = 33423359
(x - 1) | x = 00000001111111111111111111111111 = 33554431
```
Next add 1 to create a 2n number > x:
```      ((x - 1) | x) + 1 = 00000010000000000000000000000000 = 33554432
```
Lastly AND that number with x to get 0:
```      ((x - 1) | x) + 1 = 00000010000000000000000000000000 = 33554432
x = 00000001111111100000000000000000 = 33423360
(((x - 1) | x) + 1) & x = 00000000000000000000000000000000 = 0
```
Any other number without a single contigous block of 1s will fail, e.g.:
```                      x = 00000000101111000110000101001110 = 12345678
x - 1 = 00000000101111000110000101001101 = 12345677
(x - 1) | x = 00000000101111000110000101001111 = 12345679
```
The last operation did replace all the right trailing zeros with 1s (all one of them), but when adding 1 a 2n number > x is not obtained:
```      ((x - 1) | x) + 1 = 00000000101111000110000101010000 = 12345680
```
ANDing it with x does not yield 0:
```      ((x - 1) | x) + 1 = 00000000101111000110000101010000 = 12345680
x = 00000000101111000110000101001110 = 12345678
(((x - 1) | x) + 1) & x = 00000000101111000110000101000000 = 12345664
```

## Part 2 Problem

In as few steps as possible identify 2j or 2k. Obviously if you can identify one you can find the other and then use log2 to get j and k. I have a 3 step solution for 2k that is identical on the 35s/42S/16C.

Part One: my Short Solution

Here is my solution for HP16C, don't know for other models.

Thinking this one will be hard to beat :-))

```
LJ          / left justify
X<>Y        / need the result rather than the number of shifts
LAST X      / recall original value (ENTER is OK too)
B#          / ask how many bits set
XOR         / Xoring gives 0's if bits match and 1's if not
```

Paul Dale also create a 6 stepper for the 16C (above). But yours is loopless. Nice.

The 16C is an incredible machine with no clear replacement. It is the most unique calculator I own.

I knew it'd be easy on the 16C, that is why I set the challenge for the 35s/42S.

Can you do part 2?

Thanks.

Can such short programs be written to manipulate bits if the problem was using powers of 3 or powers of 5?

Namir

I do not think so.

My solution for part2 so far.
The 16C does not have the log function

```#B        =k-j
LST X
LJ        number of zeros to top
X<>Y
NOT
#B        number of zeros
X<>Y
-         =k
R/S
+         =j
```

## Part 2 Problem

In as few steps as possible identify 2j or 2k. Obviously if you can identify one you can find the other and then use log2 to get j and k. I have a 3 step solution for 2k that is identical on the 35s/42S/16C.

## Part 2 Solution

Here is my 3 step solution for 2k.
```ENTER
+/-
AND
```
To find 2k we just need to isolate the last bit, e.g.:
```       x = 00000001111111100000000000000000 = 33423360
-x = 11111110000000100000000000000000 = -33423360
(-x) & x = 00000000000000100000000000000000 = 131072
```
Thanks for playing.

 Possibly Related Threads... Thread Author Replies Views Last Post HPCC Mini Conference 2013 hugh steers 6 544 09-13-2013, 04:27 PM Last Post: BruceH 33s, 35s & 42s--The Timex(R) Factor Matt Agajanian 7 596 09-13-2013, 12:28 AM Last Post: Matt Agajanian Picture from the Mini-HHC (LA) Geir Isene 11 819 07-07-2013, 01:06 PM Last Post: Jim Horn My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 2,479 03-07-2013, 03:44 AM Last Post: Walter B WP 34S mini-challenge (B) Gerson W. Barbosa 17 1,029 12-27-2012, 04:39 PM Last Post: Marcus von Cube, Germany Maximum number of program steps in HP-42S, 33S, and 35S? Walter B 3 410 12-18-2012, 03:44 PM Last Post: Eric Smith Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 1,042 10-05-2012, 10:36 PM Last Post: David Hayden HP41 / SY41CL Mini-B USB Power Connector (Module) Matt Kernal 5 1,287 07-08-2012, 06:23 PM Last Post: Diego Diaz HP-15C (& LE!) 11-11-11 Mini-Challenge Valentin Albillo 28 1,545 11-14-2011, 08:12 AM Last Post: Valentin Albillo Mini challenge. CEIL / FLOOR in RPN M. Joury 47 2,730 10-31-2011, 10:11 AM Last Post: M. Joury

Forum Jump: 