标签: number-theory

几个月前我在纽约接受了一家对冲基金公司的采访,不幸的是,我没有获得数据/软件工程师的实习机会.(他们还要求解决方案使用Python.)

我几乎搞砸了第一个面试问题......

问题:给定一个百万个数字的字符串(例如Pi),写一个函数/程序,返回所有重复的3位数字和大于1的重复次数

例如:如果字符串是:123412345123456那么函数/程序将返回:

123 - 3 times
234 - 3 times
345 - 2 times

我在面试失败后没有给我解决方案,但他们确实告诉我,解决方案的时间复杂度始终为1000,因为所有可能的结果都在:

000 - > 999

既然我正在考虑它,我认为不可能提出一个恒定的时间算法.是吗？

我已经有了素数因子化(对于整数),但现在我想用高斯整数来实现它,但我该怎么做呢？谢谢!

我想计算一下:

a ^{b c d ...}mod m

你知道任何有效的方法,因为这个数字太大但a,b,c,...和m适合一个简单的32位int.

有任何想法吗？

警告:这个问题是由寻找不同^b模m.

另请注意,^{b c}与(a ^b)^c不同.后者等于^bc.指数是右关联的.

我想知道下面解释的任务是否在理论上是可行的,如果是这样,我怎么能做到.

给你一个N元素空间(即0和之间的所有数字N-1.)让我们看看那个空间上所有排列的空间,然后调用它S.可以标记的i第th个成员是带有词典编号的排列.SS[i]i

例如,如果N是3,那么S这个排列列表是:

S[0]: 0, 1, 2
S[1]: 0, 2, 1
S[2]: 1, 0, 2
S[3]: 1, 2, 0
S[4]: 2, 0, 1
S[5]: 2, 1, 0

(当然,当看到一个大的时候N,这个空间变得非常大,N!确切地说.)

现在,我已经知道如何通过其索引号来获得排列i,并且我已经知道如何反转(得到给定排列的词典编号.)但我想要更好的东西.

一些排列本身可能很大.例如,如果你正在看N=10^20.(的大小S将是(10^20)!我相信这是我在一个堆栈溢出问题提起过的最大号:)

如果你只是在那个空间上看一个随机的排列,那么你将无法将整个东西存储在你的硬盘上,更不用说通过词典编号来计算每个项目了.我想要的是能够对该排列进行项目访问,并获得每个项目的索引.也就是说,给定N和i指定一个排列,有一个函数接受一个索引号并找到该索引中的数字,另一个函数接受一个数字并找到它所在的索引.我想这样做O(1),所以我不需要在排列中存储或迭代每个成员.

你说疯了吗？不可能？那可能.但请考虑一下:像AES这样的分组密码本质上是一种排列,它几乎完成了我上面概述的任务.AES具有16个字节的块大小,这意味着N是256^16它是围绕10^38.(S重要的是,它的大小是一个惊人的(256^16)!,或者说是围绕着10^85070591730234615865843651857942052838 …

我想在Python中采用像[[1,2],[3,4]] mod 7这样的矩阵的模逆.我看过numpy(它进行矩阵求逆而不是模块矩阵求逆),我在网上看到了一些数论包,但似乎没有什么比较常见的程序(至少对我而言似乎相对常见).

顺便说一下,上述矩阵的逆是[[5,1],[5,3]](mod 7).我希望Python能为我做这件事.

有没有算法算(1^x + 2^x + 3^x + ... + n^x) mod 1000000007？
注意:a^b是a的b次方.

约束是1 <= n <= 10^16, 1 <= x <= 1000.所以N的值非常大.

我只能解决O(m log m)if m = 1000000007.它非常慢,因为时间限制是2秒.

你有任何有效的算法吗？

有评论说它可能与这个问题重复,但它肯定是不同的.

我有一个系列

S = i^(m) + i^(2m) + ...............  + i^(km)  (mod m)   

0 <= i < m, k may be very large (up to 100,000,000),  m <= 300000

我想找到这笔钱.我不能应用几何级数(GP)公式,因为那时结果将具有分母,然后我将不得不找到可能不存在的模逆,(如果分母和m不是互质的).

所以我做了一个替代算法,假设这些功率将使一个长度小于k的周期(因为它是一个模块化方程式,所以我会得到类似2,7,9,1,2,7,9的东西, 1 ....)并且该循环将在上述系列中重复.因此,我不是在0到k之间迭代,而是在一个周期中找到数字的总和,然后计算上述系列中的周期数并将它们相乘.所以我先找到i^m (mod m)然后再乘以这个数字,然后在每一步取模数直到我再次到达第一个元素.

但是当我实际编码算法时,对于i的某些值,我得到了非常大的周期.因此在终止之前花费了大量时间,因此我的假设是不正确的.

那么我们还能找到其他模式吗？(基本上我不想迭代k.)所以请给我一个有效的算法来找到总和.

我希望实现一个具有指定周期的简单伪随机数发生器(PRNG),并确保在该周期的持续时间内没有冲突.经过一番研究后,我发现了非常着名的LCG,这是完美的.问题是,我无法理解如何正确配置它.这是我目前的实施:

    function LCG (state)
    {
        var a = ?;
        var c = ?;
        var m = ?;

        return (a * state + c) % m;
    }

它表示,为了使所有种子值都有一个完整的时间段,必须满足以下条件:

1. c和m是相对素数
2. a-1可被m的所有素因子整除
3. 如果m是4的倍数,则a-1是4 的倍数

1和3很容易理解和测试.然而,2,我不太明白这意味着什么或如何检查它.那么C,它可以为零吗？如果它不是零怎么办？

总的来说,我需要选择A,C和M,使得我的周期为48 ^ 5 - 1.M等于期间,我不确定A和C.

什么是最有效的算法,任何人都可以想到,给定一个自然数n,返回最小自然数x与n个正除数(包括1和x)？例如,给定4算法应该得到6(除数:1,2,3,6); 即6是具有4个不同因子的最小数字.同样,给定6,算法应该得到12(除数:1,2,3,4,6,12); 即12是具有6个不同因子的最小数字

就真实世界的性能而言,我正在寻找一种可扩展的算法,它可以在一台可以每秒进行10 ^7次计算的机器上在2秒内给出10 ^20的答案.

生成素数是一个玩具问题,我经常不时尝试,特别是在尝试新的编程语言,平台或风格时.

我正在考虑尝试使用Hadoop(Map Reduce)编写素数生成算法或素数测试算法.

我想我会发布这个问题,以获得提示,参考,算法,方法.

虽然我的主要兴趣是基于Map Reduce的算法,但我不介意查看新的Hadoop编程模型或者例如查看使用PiCloud

我在Prime数字生成中似乎有一些有趣的问题:这里,这里和这里,但没有任何与Parallel方法相关的问题引起了我的注意.

提前致谢.