MS Excel Die Hard

Question

You are John McLane, and Simon Gruber is back in town.
This time he booby trapped 50 nuclear power plants across the US, and sent you a laptop he prepared, along with the following note:

Any attempt to breach any rule will trigger the fireworks. Don't test me.

• you can only run microsoft excel
• no add in allowed
• no external device
• when your sheet is ready, if I type in any positive integer ≤ 1 000 000 in cell A1, I want to see its prime factor decomposition once it has finished running
• you have 3 free formulas. For every formula you use above 3, I will blow up one plant. (one formula occupies one cell and starts with the '=' sign)
• you have 10 free static values, including the integer to be decomposed in cell A1. Any static value you use above 10, I will blow up one plant. (static values don't start with '=')
• during the development process, you are free to use as many formulas and static values as you want. I will count how many cells are used only once the sheet is finished
• an array formula of (n,m) cells is considered n*m formulas
• sheet recalculations are free (shift+f9)
• Oh, and I almost forgot: only spreadsheet calculations, no vba, no programming

How many nuclear plants are you able to save McLane?

Answer 1

Well, if I really, really had to do this then I guess I would

go into Options and under Formulas I would set "Enable iterative calculation" with Maximum Iterations set to 1.

I need the following:

Cell B1 contains

the formula =IF(B1=0,A1,IF(MOD(B1,C1)=0,B1/C1,B1)) this gives us the dividend after dividing by each prime factor which is found in C1

Cell C1 contains

the formula =IF(C1=0,2,IF(MOD(B1,C1)=0,C1,C1+1)). This is the current trial divisor. If this is a factor, then B1 is divided by this and the C1 is not updated, otherwise the C1 is incremented by 1. C1 is not guaranteed to be prime. We could be more efficient by having a list of primes as in my previous solution.

I'm keeping it simple this time.

To finish, cell D1 contains

the formula =IF(AND(B1=1,RIGHT(D1,1)="*"),LEFT(D1,LEN(D1)-1),IF(MOD(B1,C1)=0,IF(D1=0,C1&"*",CONCATENATE(D1,C1,"*")),IF(D1=0,"",D1))). The first part removes the trailing "*" when the factorization is complete. The second part concatenates the factor to the existing string (the D1=0 part covers the start of the string)

Simply press Shift-F9 until B1=1 and cell D1 will contain the prime factorization. It is possible to reduce the number of recalculations by putting in a check for when C1 > SQRT(A1) and by having a list of primes. I have left these out for simplicity of coding.

Answer 2

Extra answer 1: using 1 formula only

Firstly

go to Options and under Formulas I would set "Enable iterative calculation" with Maximum Iterations set to 32767 (max value)

Then

name the input range in and output range out

Enter the following formula in out

=IF(ISERROR(out),in&"#"&in&"#"&"2"&"#",IF(VALUE(LEFT(out,FIND("#",out)-1))<>in,in&"#"&in&"#"&"2"&"#",IF(AND(MID(out,FIND("#",out)+1,FIND("#",out,FIND("#",out)+1)-FIND("#",out)-1)<>"1",MOD(MID(out,FIND("#",out)+1,FIND("#",out,FIND("#",out)+1)-FIND("#",out)-1),MID(out,FIND("#",out,FIND("#",out)+1)+1,FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)-FIND("#",out,FIND("#",out)+1)-1))=0),in&"#"&MID(out,FIND("#",out)+1,FIND("#",out,FIND("#",out)+1)-FIND("#",out)-1)/MID(out,FIND("#",out,FIND("#",out)+1)+1,FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)-FIND("#",out,FIND("#",out)+1)-1)&"#"&MID(out,FIND("#",out,FIND("#",out)+1)+1,FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)-FIND("#",out,FIND("#",out)+1)-1)&"#"&IF(RIGHT(out,1)<>"#",RIGHT(out,LEN(out)-FIND("#",out,FIND("#",out,FIND("#",out)+1)+1))&"*","")&MID(out,FIND("#",out,FIND("#",out)+1)+1,FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)-FIND("#",out,FIND("#",out)+1)-1),in&"#"&MID(out,FIND("#",out)+1,FIND("#",out,FIND("#",out)+1)-FIND("#",out)-1)&"#"&IF(MID(out,FIND("#",out)+1,FIND("#",out,FIND("#",out)+1)-FIND("#",out)-1)="1",1,IF(VALUE(MID(out,FIND("#",out,FIND("#",out)+1)+1,FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)-FIND("#",out,FIND("#",out)+1)-1))>SQRT(MID(out,FIND("#",out)+1,FIND("#",out,FIND("#",out)+1)-FIND("#",out)-1)),MID(out,FIND("#",out)+1,FIND("#",out,FIND("#",out)+1)-FIND("#",out)-1),IF(MID(out,FIND("#",out,FIND("#",out)+1)+1,FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)-FIND("#",out,FIND("#",out)+1)-1)="2",MID(out,FIND("#",out,FIND("#",out)+1)+1,FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)-FIND("#",out,FIND("#",out)+1)-1)+1,MID(out,FIND("#",out,FIND("#",out)+1)+1,FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)-FIND("#",out,FIND("#",out)+1)-1)+2)))&"#"&RIGHT(out,LEN(out)-FIND("#",out,FIND("#",out,FIND("#",out)+1)+1)))))

Note that

- this answer has a reset mechanism that will restart the process upon typing a new input
- you can turn on auto calculation and enjoy the show with numbers much greater than 10^6

How it works

Using circular referencing, we managed to fit all variables used in the calculation in one string value, using a # separator. (e.g. 4294180887#1#1#3*29*49358401)

The fact that the formula constantly parses itself in order to gather the content of the variables makes it particularly unreadable.

How I built it

In order to build it, I wrote the formula with variable names: if(iserror(out),in&"#"&in&"#"&"2"&"#",if(value(initval)<>in,in&"#"&in&"#"&"2"&"#",if(and(currentnumber<>"1",mod(currentnumber,currentdivisor)=0),in&"#"&currentnumber/currentdivisor&"#"&currentdivisor&"#"&if(right(out,1)<>"#",decomp&"*","")&currentdivisor,in&"#"&currentnumber&"#"&if(currentnumber="1",1,if(value(currentdivisor)>sqrt(currentnumber),currentnumber,if(currentdivisor="2",currentdivisor+1,currentdivisor+2)))&"#"&decomp)))

Then

I mapped each variable name with its formula equivalent, e.g. currentnumber = MID(out,FIND("#",out)+1,FIND("#",out,FIND("#",out)+1)-FIND("#",out)-1)

Answer 3

I'm not sure how excel handles circular references, but below is the basic idea. I'm assuming that the formulas start out being null, which then gets treated as zero, so I have +2 to get the first prime. Also, to aid readability, I'm using the naming feature, e.g. A1's name = "number_to_factor".

current_number = if(factorization="",number_to_factor,if(mod(current_number,(current_divisor+2))=0,current_number/(current_divisor+2),current_number))

.

factorization = if(mod(current_number,current_divisor+2)=0,factorization&"*"&(current_divisor+2),factorization)

.

current_divisor = if(mod(current_number,current_divisor+2) = 0,current_div,current_divisor+1)

Of course, I've probably just fallen into his trap, and by focusing on how to solve this challenge, I've been distracted from his real plan.

ETA a more general statement:

Given sheet1 and sheet2, it's possible to save sheet1 in a single cell of sheet2: just save sheet1 as a csv, then take the result and put it as a string in sheet2. Since it's saved as a csv, all the data is static, and formulas will not be evaluated. However, you can save the formulas as strings in sheet1, and then use the EVAL function to evaluate them within sheet2. Furthermore, you can have a lookup table of formulas and formula index in sheet1. In sheet2, you can take the formula index, find the formula that corresponds to that index, and then evaluate that formula, all in one cell. You can create a Turing machine in sheet1, and then run that machine in sheet2. So depending on how Excel handles circular references, it may be possible to create a Turing Complete worksheet with the restrictions given in this puzzle.

Answer 4

This feel wrong, but I can't find where it doesn't comply with the rules:

John McLane can precalculate all decompositions and type them in a lookup table.