确定十进制扩展中最长的重复周期 [英] Determing longest repeating cycle in a decimal expansion

问题描述

今天，我遇到了这篇有关十进制扩展的文章，我立刻被启发去重新设计解决方案.关于 Project Euler Problem 26 (项目欧拉问题26 )，以包括更有效的解决方案(无暴力破解).简而言之，问题在于在表达式"1/d"中找到范围为1-1000的d值，该值将使重复循环的长度最大化.

Today I encountered this article about decimal expansion and I was instantaneously inspired to rework my solution on Project Euler Problem 26 to include this new knowledge of math for a more effecient solution (no brute forcing). In short the problem is to find the value of d ranging 1-1000 that would maximize the length of the repeating cycle in the expression "1/d".

无需对这个问题做任何进一步的假设，就可以进一步提高解决我决定坚持的问题的效率.

Without making any further assumptions about the problem that could further improve the effecienty of solving the problem I decided to stick with

10^s=10^(s+t) (mod n)

这使我可以为D的任何值找到最长的重复周期(t)和周期的起点(s).

which allows me for any value of D to find the longest repeating cycle (t) and the starting point for the cycle (s).

问题在于方程的必要部分，因为这将在使用模数将其减小之前生成非常大的值.没有整数值可以处理这么大的值，并且浮点数据类型似乎在计算错误.

The problem is that eksponential part of the equation, since this will generate extremely large values before they're reduced by using modulus. No integral value can handle this large values, and the floating point data types seemes to be calculating wrong.

我当前正在使用此代码:

I'm using this code currently:

Private Function solveDiscreteLogarithm(ByVal D As Integer) As Integer
Dim NumberToIndex As New Dictionary(Of Long, Long)()
Dim maxCheck As Integer = 1000

For index As Integer = 1 To maxCheck
   If (Not NumberToIndex.ContainsKey((10 ^ index) Mod D)) Then
        NumberToIndex.Add((10 ^ index) Mod D, index)
   Else
        Return index - NumberToIndex((10 ^ index) Mod D)
   End If
Next

Return -1
End Function

在某点将计算(10 ^ 47)mod 983"，结果为783，这不是正确的结果.正确的结果应该是732.我认为这是因为我使用的是整数数据类型，并且会导致溢出.我尝试使用double代替，但是结果甚至更奇怪.

which at some point will compute "(10^47) mod 983" resulting in 783 which is not the correct result. The correct result should have been 732. I'm assuming it's because I'm using integral data types and it's causing overflow. I tried using double instead, but that gave even stranger results.

那我有什么选择?

推荐答案

我将使用乘法来进行for循环，而不是使用^来执行幂运算，然后通过使用条件运算来获取数字的mod检查计算的数字是否大于mod.这有助于使数字更小，并保持在您的Mod号码范围内.

Instead of using ^ to do your powers, I would do a for loop using multiplication and then taking the mod of the number as you go along by using a conditional to check if the number calculated is greater than the mod. This helps to keep the numbers smaller and within range of your mod number.

这篇关于确定十进制扩展中最长的重复周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！