6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ this is like an excel homework than a puzzle :) $\endgroup$ – Oray Sep 24 '17 at 11:06
  • $\begingroup$ @Oray no teacher in their right mind would give a homework so difficult :-) $\endgroup$ – sousben Sep 24 '17 at 11:14
  • 2
    $\begingroup$ How are you supposed to get up to 19 cells of output with only 10 formulas? $\endgroup$ – boboquack Sep 24 '17 at 11:27
  • $\begingroup$ @boboquack actually you have 53 formulas before all plants have exploded. I'm curious to see how people try to resolve it before I give a first hint $\endgroup$ – sousben Sep 24 '17 at 11:35
  • 1
    $\begingroup$ What counts as "seeing its prime factor decomposition"? E.g., what if I see one prime factor in cell D6, and each time I hit shift-F9 I get a new one until they've all been shown? $\endgroup$ – Gareth McCaughan Sep 24 '17 at 15:06
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Try 262144 as input. $\endgroup$ – LeppyR64 Sep 25 '17 at 14:59
  • $\begingroup$ Yeah, 9 is the wrong number. On the other hand, it's pretty trivial to modify this to use the right number (which I think is 19) instead. $\endgroup$ – Gareth McCaughan Sep 25 '17 at 15:13
  • $\begingroup$ What happens if you enter 1009 (the first prime after 1000)? It doesn't have any of the 168 primes as factors, so wouldn't all the exponents be zero in the result? $\endgroup$ – 2012rcampion Sep 25 '17 at 15:38
  • $\begingroup$ @2012rcampion True, that. You would need a list of all primes less than 1,000,000. I will think. $\endgroup$ – Hugh Meyers Sep 25 '17 at 15:49
  • 1
    $\begingroup$ @LeppyR64 Yes. I will update when I can. $\endgroup$ – Hugh Meyers Sep 25 '17 at 16:57
2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Wow. I'm not really an Excel guy, so I went for something simple. This is impressive. Does this mean that Simon Gruber actually has to build two new nuclear power plants? $\endgroup$ – Hugh Meyers Sep 27 '17 at 6:39
  • $\begingroup$ @HughMeyers Ahah he certainly didn't expect to be beaten at his own game! I think what's interesting with this puzzle is that it illustrates that enabling that calculation feature in excel makes a spreadsheet Turing complete without vba $\endgroup$ – sousben Sep 27 '17 at 7:00
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Circular references freeze the cells which are self-dependent $\endgroup$ – boboquack Sep 25 '17 at 2:41
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ the lookup table would use millions of static values $\endgroup$ – sousben Sep 25 '17 at 8:00
  • $\begingroup$ I thought of this too; but there's a per-cell character limit, so you couldn't fit them all in one cell either. $\endgroup$ – 2012rcampion Sep 25 '17 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.