I remember from a long time ago (about 40 years, believe it or not) learning how to convert a repeating decimal into a fraction... like .33333... = 1/3. That one is obvious, but what about something like .571428571428... = 4/7?

Can anyone show me the procedure for that?

Then, a peripherally related question. First a bit of background. My software at work has hidden menus that can only be accessed with help from technical support, things like to "unpost a transaction from accounts receivable" or "reset conflict flags". Stuff that the end user isn't supposed to do without assistance. And I don't do these things without their help. But I couldn't resist the challenge of accessing those hidden menus.

Their method is this: I key in the magical access request code (Shift-F9), and it generates a random number. I read this number to the tech support guy (superb technical support, by the way -- should be, we're paying almost $800 a month licensing fee for the software!) and he reads back the reply number which I key in, and voila! I'm at the hidden menu.

They have assured me that I will never be able to figure out the algorithm for generating that reply number. Imagine their surprise when I informed them last week that multiplying their random number by .9153818 and discarding everything in the result to the right of the decimal point, I got a number that accessed the hidden menus.

This loosened their tongues enough to admit to me that while my method worked, it was not how they generated their number. They multiply the random number by an integer, then divide that number by another integer to get their access number. That would be the same as multiplying by a fraction.... wouldn't it? But what kind of fraction could be multiplied by a random integer and give an integer result? Could .9153817 plus a few more digits be part of a repeating decimal that could be turned into a fraction?

As I said, they were surprised when I came up with the .9153818 thing, but they will be truly astonished if I can reverse-engineer their method of generating the reply number and come up with the multiplicand and divisor for their random number. I am guessing that there are no more than three digits in either number, because they come up with the answer just about as fast as I can read them the query.

The .9153818 always generates a number slightly larger than the integer required for access (thus, my dropping of the digits to the right of the decimal). Now the question: Given the above information, how do they generate their integer answer to the random number query?

Below are samples of the random number, followed by the reply number:

8465857 7749491
4457902 4080682
3331257 3049372
4469755 4091532
5227746 4785383
9595194 8783265

Any ideas?

tanstaafl.

Well, I'm not much of a mathmetician, but I think anybody could figure out that if you divide the second number by the first number, you come up with your "magic number" every time.

I searched around on the internet for "decimal to fraction conversion" and came across an interesting site that had a piece of java that does it on the fly. It starts out with the smallest fraction and gets increasingly more precise. Check it out.

Another site I found listed some common fractions that you can round to.

Anyways, if I were the company, I'd find a slightly better algorithm than that...

and this: http://acm.uva.es/problemset/v3/332.html

~Yogi.

FYI, based on the output from the first link, the most precise fraction that is common amongst all the numbers is 2434/2659.

If you multiple any of the first numbers by 2434, then divide by 2659, you'll get a number that, when rounded, results in the second number.

I'm curious, though, if they do any rounding with their result, or if they have two integers that always result in a whole number. I highly doubt it. Is that even possible for all sets of the two numbers? Maybe somebody here loves math and can answer that?

that is the most ridiculously insecure scheme of generating an unlock code I've ever heard. unbelievable.

that is the most ridiculously insecure scheme of generating an unlock code I've ever heard. unbelievable.

True, it isn't very secure. But keep in mind, the only reason they keep those menus hidden is for the protection of the end user, not the protection of themselves. Absolutely the only thing I could accomplish by accessing those hidden menus without qualified assistance is to damage my own data. And that would be my problem, not theirs. There are no "secrets" or enhanced capabilities or anything like that in those menus, just things too "dangerous" for unqualified users to be given access.

tanstaafl.

I searched around on the internet for "decimal to fraction conversion" and came across an interesting site that had a piece of java that does it on the fly

That's good, but not what I'm looking for. There is a relatively simple pencil and paper way to do it. I can remember a tiny bit of it... like if I had a 4-digit repeating sequence (like .12341234...) I would start out doing something like writing down 1234/1000 and moving the decimal... oh, hell, I can't remember, just that it was a really neat and totally non-intuitive process.

tanstaafl.

the most precise fraction that is common amongst all the numbers is 2434/2659.

Hmm... that's a good one. And, if I set my adding machine to integer only (set number of decimal places to "0" instead of "2" or "Float") and do the division first, then the multiplication (to avoid overflow) I get an integer answer that works. That may be how they're doing it. I'll email them tonight and see if I strike any nerves.

tanstaafl.

The procedure for reducing a repeating decimal fraction to a proper fraction is thus:

First, assign x to be equal to the repeating fraction:

x = 0.571428(571428 ...)

Next, figure out the repeating decimal period. In this case, it repeats every six digits. Write down the fact that 10^(period)x equals whatever it equals:

1000000x = 571428.571428(571428 ...)

Now you have two equations. If you subtract the first equation from the second equation, the fraction cancels itself out, since it repeats to infinity in both numbers:

1000000x - x = 571428.571428(571428 ...) - 0.571428(571428 ...)
999999x = 571428

Now just solve for x and reduce the fraction to normal form:

x = 571428/999999 = 4/7

By the way, the traditional algorithm for finding the greatest common divisor (which is very useful in reducing fractions) is the Euclidean algorithm, which can be defined thusly:

def euclid(a, b):

   if b == 0:

      return a

   else:

      return euclid(b, a mod b)

Also, repeating decimals are traditionally shown by simply drawing a line over the repeating part, but I don't have that facility here. I was going to use an underline, but since HTML has been disabled ....

Now, I'd have to take exception to your assumption that the numbers must be small. If it's something that they do often enough, I'm sure that they bothered to write a simple application to allow them to type in the number and return the resultant number without them having to do it by hand. The fact that they know what the function is does not mean that they are applying it by hand.

On the other hand, the fact that they don't realize that multiplying by one number and dividing by another is nearly the definition of a fraction doesn't speak highly of their intelligence. And there are any number of one-way functions that would be as easy to program and much more secure.

I remember from a long time ago (about 40 years, believe it or not) learning how to convert a repeating decimal into a fraction... like .33333... = 1/3. That one is obvious, but what about something like .571428571428... = 4/7?

Well, if you have a repeating decimal, you can transform that into a (non-minimal) fraction by deviding the x positions long prepeating part by an as long sequence of 9s. In your example: 0.3333... has the single position repeating sequence of "3", so you devide 3/9, which is obviously equal to 1/3. 0.5714285714... has a 6 position repeating pattern, so you devide 571428/999999 which simplifies to 4/7. To simplify, you should use euklids algorithm like posted by wfaulk.

cu,
sven

that is the most ridiculously insecure scheme of generating an unlock code I've ever heard. unbelievable.

I've got a better story than that.

A few years ago, we bought Cheyenne's "Arcserve 6.0" for server tape backups. (Great piece of software, by the way, and Cheyenne has since been bought by Computer Associates and the product has been renamed to ArcserveIT.)

We bought two copies of the "Single Server Edition", to run on two servers. That way we were in license compliance with the software. I just stuck one of them on the shelf, thinking I would never need to open the box. Just use the one CD I had in my hand to install it on both servers.

To my surprise, it wouldn't let me install the second copy on the second server. Seems it goes checking on the network to compare its CD key with any other running copies it finds on the network. Nice little protection feature, bravo Cheyenne. Score one for your team.

But get this...

Since the second box was already retired to the software library shelf in a different area of the building, I decided I would do the second install later. Without getting up out of my chair, I happened to be browsing the Arcserve software manual. (Remember those? They used to come printed and bound in the box with the software.) In the "installation" section of the manual, there were very detailed screen shots of each stage of the installation procedure. One of the screen shots was of the CD-key entry screen. With a complete CD key typed into the boxes on the screen.

"What the hell," I thought. I typed in the CD key that was shown in the installation screen shot (as opposed to the real CD key I had been supplied).

Not only did it work, but it unlocked the software so that it was now the full Enterprise edition instead of the limited Single Server edition. Now I could install as many copies of the software as I wanted, using that Enterprise key. Not only that, but a bunch of great new features were unlocked in the software, too.

I wonder if anyone got sacked over that one?

I wonder if anyone got sacked over that one?

Those responsible for sacking the people who have just been sacked have been sacked.

In reply to:

---

That's good, but not what I'm looking for. There is a relatively simple pencil and paper way to do it. I can remember a tiny bit of it... like if I had a 4-digit repeating sequence (like .12341234...) I would start out doing something like writing down 1234/1000 and moving the decimal... oh, hell, I can't remember, just that it was a really neat and totally non-intuitive process.

---

The approximation 2434/2659 can be obtained by using the theory of Continued Fractions. These are formulas of the form

a0+1/(a1+1/(a2+1/(a3+...)))

The basic idea is to note that

0.9153818 = 0+1/(1+1/(10+1/(1+1/(4+1/(2+1/(20+1/(1+1/(1+1/(3+1/(2+1/(3+1/(1+1/25))))))))))))

How did I get that horrible formula?

1/.9153818 = 1.092440335
1/.092440335 = 10.81778861
1/.81778861 = 1.222809893
1/.222809893 = 4.488131064
1/.488131064 = 2.048630119
etc., etc.

Note that in each case I take the integer part of the result and plug it into the next slot of the continued fraction, then take the reciprocal of the fractional part and repeat.

It stands to reason, and in fact can be proven, that taking the first several terms of the continued fraction provides a very good approximation to the number you started with. In this instance

2434/2659 = 0+1/(1+1/(10+1/(1+1/(4+1/(2+1/20)))))

This doesn't prove that those are the integers that they are using in the unlock code algorithm, but it does give you a way of generating possible numbers from the ratio you observed.

And I'll agree with everyone else who said that it's a stupid way of generating an unlock code.

--John

The approximation 2434/2659 can be obtained by using the theory of Continued Fractions. These are formulas of the form

a0+1/(a1+1/(a2+1/(a3+...)))


Sigh... I just wish I were smart enough to really understand that!

But I got what I needed for the fractionization of repeating decimals -- I can never remember that from one year to the next because it seems to me to be so unintuitive. Many thanks to all who helped.

And I'll agree with everyone else who said that it's a stupid way of generating an unlock code.

Well, yes and no. Remember that their objective was to make it easy for them to get in, not necessarily to keep other people out. They stand to lose nothing if some incredibly skilled hacker like myself can see through the amazingly sophisticated algorithm of dividing the answer by the query to get the multiplicand. All I can do with this unlock key is damage my own data. They just want an "out" in case I (or some other curious hacker) does that. They can say "It's not our fault you trashed your data. That'll teach you not to hack our unlock key."

tanstaafl.