May I please ask how you arrived at the magic number of 391511?
I have tried several versions of LCD's but the logic of it eludes me.
Regards
Hi. Thanks. Glad you found this interesting. Basically, I have a
program that does an automatic search for me
Basically, your output are the character codes for "BINGO", which are
66,73,78,71,79.
I used the Floor function earlier, but that was probably not the best. I
think I should have used the Ceiling function. With Ceiling (ie
CEILING(A1,15), our input numbers (1-75), are transformed into
15,30,45,60,75.
The program does a quick check of the numbers to quickly learn that there
are no solutions to this problem. It then does a quick scan of the
numbers with scaling and offset to check for a simple solution. There are
none, so it moves on.
The next step it does is to offset the input, and not the output.
However, this usually results in larger numbers than Excel's Mod function
can handle. I don't know why this isn't fixed. It causes a lot of
problems.
XL: MOD() Function Returns #NUM! Error Value
http://support.microsoft.com/kb/119083/en-us
First two solutions are:
=CHAR(MOD(3400616087,CEILING(A1,15)+52)) & A1
The program checks that "3400616087" will work, but since it is right on
the edge, it will search again for a smaller number.
=CHAR(MOD(90809279,CEILING(A1,15)+56)) & A1
other attempts result in larger numbers, so it exits this portion.
Program will then look at the output numbers.
The output numbers are larger than the input numbers, so there are no
solutions. It then offsets the input back towards 0. The first attempt
is a reduction of 66. The new output numbers are 0,7,12,5,13.
There is still no solution, so it offsets the input. The first attempt is
an offset of -14, since each input needs to be larger than similar output
number. The program will loop in a search. I call the function with a
few options, but we are in luck here on the program's first loop, as
discussed below.
I have custom functions that I call, but this is the basic idea for this
problem since you were interested. :>)
The output number is 391511. This longer version will "usually" have a
smaller number than the other examples. Therefore:
=CHAR(MOD(391511,CEILING(A1,15)-14)+66) & A1
If still no solution, the program moves on to a scaling factors between
2-10. There are usually no solutions with numbers larger than this. If
still no solution, it will then attempt to break the problem into two.
It partitions both lists into two groups via a function called
KSetPartition. (of size 2). It will then retry with both smaller sets and
lists the best solutions. If still no luck, the next partition is size 3,
and retries. If still no luck, I have the program end.
Basically, here is the logic to this problem. HTH :>)
Sub Demo()
Dim Answer
Dim Inn, Out
Dim t(1 To 5)
Dim v(1 To 5)
Dim ds
Dim m
Dim z
Dim p As Long
Inn = Array(1, 16, 31, 46, 61)
Out = Array(0, 7, 12, 5, 13) ' "BINGO" - 66
With WorksheetFunction
' Make base-1
Inn = .Transpose(.Transpose(Inn))
Out = .Transpose(.Transpose(Out))
'= = = = = = = = = = =
' Most pair of numbers within "Inn" are Relatively Prime
' except for 1 pair!!! Darn!!
' Therefore, call TaYen and attempt to reduce...
' Call Ta-Yen Rule:
' Most pairs are Relatively Prime
' However...
' 16=2^4, and 46=2*23
' Keep 16, but cancel 2 in 46(leave 23)
'ds = TaYen(Inn)
'= = = = = = = = = = =
'// Returns this array instead of Inn
ds = Array(1, 16, 31, 23, 61)
' Make base-1
ds = .Transpose(.Transpose(ds))
End With 'WorksheetFunction
' Call your LCM function, but for now...
m = [LCM(1, 16, 31, 23, 61)] 'm = 695888
For p = 1 To 5
t(p) = m / ds(p)
Next p
'// Now we need to Solve for k for each t & ds in:
'// Mod(t * k, ds)=1 for k.
'// "Should" have a solution if ds was reduced correctly...
'// There are a few interesting number theory techniques,
'// but this is the basic general idea...
For p = 1 To 5
'// t(p) may be large, so we try to reduce...
z = t(p) Mod ds(p)
If z = 0 Then
v(p) = 0
Else
v(p) = FindOne(z, ds(p))
End If
Next p
For p = 1 To 5
Answer = Answer + Out(p) * v(p) * t(p)
Next p
'// Number may not be the "least"...
Answer = Answer Mod m
Debug.Print Answer
End Sub
Function FindOne(x, y)
'/ There are better methods, but for here ...
Dim p As Long
For p = 1 To y
If ((p * x) Mod y) = 1 Then Exit For
Next p
FindOne = p
End Function