Ernie and the Unexpectedly Exposed PIN

Question

I dropped in on Ernie a few days ago. As I pushed open the door to his workshop I could hear a clanking, hissing noise and then saw Ernie emerging from a great clouds of steam, his face blackened with what looked like soot.

"Just in time to help me debug my calculator," he called out as he saw me.

"The clock-work calculator?" I asked.

"No. Clockwork is just so 20th century," Ernie retorted. "In my opinion, the future is in steam! Just let me stoke it up a little more and I can show you how it works." Ernie added a couple of shovels of coal to a small boiler and the hissing sound rose in intensity.

The calculator was a labyrinth of oily tubes, valves, gear-boxes, and brass widgets, like some sort of mechanically-augmented steam-punk tuba.

There were three long rows of clock-dials (each with a single pointer hand), each face numbered $0$ to $9$, and a small keyboard. The 14 keys were labelled with the digits 0 to 9 and the letters A, B, and D.

"If you press a series of digit buttons then the A or B button, you can load a number into the $A$ or $B$ register," he explained.

"What does the D button do?" I asked.

"That," Ernie replied, "is to test the Division and Decrement functions. The machine checks if $A$ divides perfectly into $B$ and, if it does, it completes the division and outputs $B \div A$ on the $C$ register. Then it decrements $A$ twice."

"What happens if $A$ doesn't divide into $B$?" I asked.

"Then it doesn't do anything. I haven't built in fractions or decimal points yet, and I hate approximate answers!" said Ernie.

Ernie asked me to type my 'lucky' 3-digit number into the $A$ register, but unlike Ernie I don't believe in lucky numbers, so I typed in the first number I could think of - which happened to be my auto-bank PIN $a$. When I pressed the A button, the indicator arms on the first three dials dial of the $A$ register swung round to point at the digits I had entered.

"Now enter a big number for the $B$ register," Ernie commanded. I typed in $n$ digits, but when I hit the B button, the first $n$ indicator arms all swung round to the digit $1$. Ernie muttered something about the steam pressure being too low to actuate the internal digital transfer mechanism (or maybe a sticky bypass needle actuator) but then pointed out that $b = 111111...11111$ was still a valid integer. "Try the D button now," he said.

I pressed D. The hissing and clanking rose in intensity, and the indicator arms on the $C$ register swung round wildly. After some seconds there was a mechanical "ding" and the arms froze in place, displaying a very long number in the $C$-register, and $a$ was decremented by $2$.

"Well at least Division and Decrementation work properly," said Ernie, after checking the results. "Lucky that your $a$ was a factor of that $b$. Try a few more divisions and I will see if I can sort out the problems with data-entry," he said.

So I left $a-2$ in the $A$ register and entered another number $b_2$ (of different length) into the $B$ register. Once again $b_2$ turned to all $1$s, and when D was pressed, an answer was output to register $C$ and $a-2$ was decremented to $a-4$. I repeated the process twice more without changing the $A$ register, and the same sequence of events occurred each time.

But after my fourth calculation Ernie waved me to a stop. "I think I have found part of the problem," he said. He made a small adjustment to a set of valves with a mallet and asked me to try again.

His adjustments had reset all the registers back to $0$, so I re-entered my 3-digit PIN into $A$, and entered a new $b$. My fingers were getting a bit tired from all the number pressing, so this time I just typed in a 6-digit number. But when I pressed B, there was still obviously a problem - the indicator arms all pointed at $0$s and $1$s.

"Not perfect, but better than before", Ernie said, then pointed out that I still had a valid 6-digit integer in the $B$ register and I should try the D button again.

As on all the previous occasions, $a$ divided perfectly into $b$, and after displaying an answer in the $C$ register, $a$ was replaced by $a-2$.

I repeated the process thrice more without altering the $A$ register, but typing a 7-digit, then an 8-digit, then a 9-digit number into the $B$ register (each constructed from $0$s and $1$s), and the same sequence of events occurred each time.

Eventually Ernie lamented that "...it might take a bit more thought to work out what is going wrong with data entry and decrementation, but at least it is doing the actual division perfectly." So we stopped for lunch.

"I suppose you will be telling this story on the web," he commented after we had eaten. I was surprised and a little embarrassed because I hadn't realized Ernie had even known about my stories. But Ernie reassured me that he didn't mind his 'web-presence'. "But if I can make a suggestion," he continued, "it might be safest to change your PIN if you are going to tell the story exactly as it happened."

Well - I did change my PIN even though I couldn't see how it could possibly be determined from my story. I'm guessing that Ernie was just playing a practical joke on me.

Can anybody tell me if it really is possible to calculate my old PIN from what I have told you?

Answer 1

If a number is even, it's never going to divide a number that is all 1s. Similarly, a number that is divisible by 5 also isn't going to divide all 1s. So a, a-2, a-4, and a-6 are all odd and not divisible by 5. The only way that this is possible is if a ends in 3. This section gives us no further information, since every number that is relatively prime to 10 will divide a repunit of some length.¹

I couldn't come up with a neat way to do the second part, so I ran a brute force search of all 3-digit factors ending in 3 of 6-digit numbers consisting of 1s and 0s. This was the result:

143 divides 100100, 101101, 110110, 111111
183 divides 100101
193 divides 110010
213 divides 100110
273 divides 101010, 111111
393 divides 101001
653 divides 111010
803 divides 110011

Then, I tested the corresponding $a$-2 values with 7-digit numbers:

141 divides 1001100, 1011111
181 divides 1001111
271 divides 1011101, 1111100

And then the 8-digit numbers:

179 divides 11010111

Just to check:

177 divides 100101111, 101110011

The PIN must be 183.

---

¹Proof from Wikipedia (https://en.wikipedia.org/wiki/Repunit#Properties):

Using the pigeon-hole principle it can be easily shown that for each $n$ and $b$ such that $n$ and $b$ are relatively prime, there exists a repunit in base $b$ that is a multiple of $n$. To see this consider repunits $R_1^{(b)},...,R_n^{(b)}$. Assume none of the $R_k^{(b)}$ is divisible by $n$. Because there are $n$ repunits but only $n-1$ non-zero residues modulo $n$ there exist two repunits $R_i^{(b)}$ and $R_j^{(b)}$ with $1\le i<j\le n$ such that $R_i^{(b)}$ and $R_j^{(b)}$ have the same residue modulo $n$. It follows that $R_j^{(b)} - R_i^{(b)}$ has residue $0$ modulo $n$, i.e. is divisible by $n$. $R_j^{(b)} - R_i^{(b)}$ consists of $j - i$ ones followed by $i$ zeroes. Thus, $R_j^{(b)} - R_i^{(b)} = R_{j-i}^{(b)}\times b^i$. Since $n$ divides the left-hand side it also divides the right-hand side, and since $n$ and $b$ are relatively prime, $n$ must divide $R_{j-i}^{(b)}$, contradicting the original assumption.

Answer 2

Building off of f" answer:

The machine converted Ernie's big numbers into giant strings of 1's, but these 1's were in fact divisible by his secret code. Thus we need to confirm the following 4 things to in fact show that 181 does work:

183 * some 1st giant number = some giant amount of 1's
181 * some 2nd giant number = some giant amount of 1's
179 * some 3rd giant number = some giant amount of 1's
177 * some 4th giant number = some giant amount of 1's

Also I should note that these are not unique. Instead the numbers below are the "smallest" which work.

I wrote a macro in excel to find these giant numbers after figuring out the 183 only to find that f" beat me to it.

Our input number for 183 is only:
607164541590771098967820279295689131754705525197328476017
which can be confirmed using Wolfram Alpha here.

Our input number for 181 is:
613873542050337630448127685696746470227133210558624923265807243707796193984039287906691221608348680171884591774094536525475751995089011663597298956414978514426028238182934315531
which can be confirmed using Wolfram Alpha here.

Our input number for 179 is:
6207324643078833022967101179391682184978274363749224084419615145872129112352576039726877715704531346989447548106765983860955927995034140285536933581626319056486654252017380509
which can be confirmed using Wolfram Alpha here.

Finally, our input number for 177 is:
627746390458254865034526051475204017576898932831136220966729441305712492153170119271814187068424356559949780288763339610797237915881983678593848085373509102322661644695543
which can be confirmed using Wolfram Alpha here.

---EDIT---
Since I had written the script, I wanted to look at all numbers 1000 digits or less that could be divided by 183, 181, 179, and 177. (The smallest of which is listed above).

177: 171, 345, 519, 693, 867 digits (a repeating cycle of 174 digits)
179: 175, 353, 531, 709, 887 digits (a repeating cycle of 178 digits)
181: 177, 357, 537, 717, 897 digits (a repeating cycle of 180 digits)
183:  57, 117, 177, 237, 297 digits (a repeating cycle of  60 digits)

I was wondering if anyone knew how to predict the length of the number/cycle?