如果我们考虑尝试给出最有效答案的附加约束，即给定一个长度为m(1-5)的均匀分布整数的输入流I，输出一个长度为m(1-7)的均匀分布整数的流O，长度为L(m)。

最简单的分析方法是将流I和O分别视为5元数和7元数。这是通过主答案的思想来实现的，即取流a1, a2, a3，…- > a1 + a2 + 5 * 5 ^ 2 * a3 + . .流O也是如此。

然后如果我们取长度为m的输入流的一段，选n s.t, 5^m-7^n=c，其中c>0，且尽可能小。然后有一个从长度为m的输入流到1到5^m的整数的统一映射，还有一个从1到7^n的整数到长度为n的输出流的统一映射，当映射的整数超过7^n时，我们可能不得不从输入流中丢失一些情况。

这就给出了L(m)的值约为m (log5/log7)也就是。82米。

上述分析的难点是方程5^m-7^n=c，它不容易精确求解，而在1到5^m的均匀值超过7^n的情况下，我们失去了效率。

问题是如何接近m (log5/log7)的最佳可能值。例如，当这个数字接近一个整数时，我们能否找到一种方法来实现这个精确的整数值输出?

如果5^m-7^n=c，那么从输入流中，我们有效地生成了一个从0到(5^m)-1的均匀随机数，并且不使用任何高于7^n的值。但是，这些值可以被保存并再次使用。它们有效地生成了从1到5^m-7^n的统一数字序列。所以我们可以尝试使用这些，并将它们转换成7位数，这样我们就可以创建更多的输出值。

如果我们让T7(X)是由大小为X的均匀输入导出的随机(1-7)整数的输出序列的平均长度，并假设5^m=7^n0+7^n1+7^n2+…+ 7 ^ nr + s, s < 7。

那么T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)因为我们有一个无长度序列，概率为7^n0/5^m，残差长度为5^m-7^n0，概率为(5^m-7^n0)/5^m)。

如果我们一直代入，我们得到:

T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m  = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m

因此

L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)

另一种说法是:

If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)

最好的情况是上面的原始情况，即5^m=7^n+s，其中s<7。

然后机械师》(5 ^ m) = nx (7 ^ n) / (7 ^ n + s) = o (n + 1) = m (Log5 / Log7) + o(1)美国之前。

最坏的情况是我们只能找到k和s.t 5^m = kx7+s。

Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)

其他情况介于两者之间。看看对于很大的m，我们能做得多好，也就是说，我们能多好地得到误差项，这将是很有趣的:

T7(5^m) = m (Log5/Log7)+e(m)

一般来说，似乎不可能实现e(m)=o(1)但希望我们可以证明e(m)=o(m)。

整个问题取决于5^m的7位数字对不同m值的分布。

我相信有很多理论涵盖了这一点，我可能会在某个时候看一看并报告。

这里我们使用约定的rand(n) -> [0, n - 1]

从我读到的许多答案中，它们要么提供了一致性，要么提供了暂停保证，但不能同时提供(adam rosenfeld的第二个答案可能)。

然而，这样做是可能的。我们基本上有这样的分布:

这给[0-6]上的分布留下了一个漏洞:5和6没有 发生的概率。想象一下，现在我们试图通过移动 概率分布和求和。

事实上，我们可以把初始分布平移1，然后 重复将得到的分布与移位的初始分布相加 2，然后3，以此类推，直到7，不包括在内(我们涵盖了整个范围)。 如下图所示。颜色的顺序，对应 步骤，是蓝色->绿色->青色->白色->品红->黄色->红色。

因为每个插槽由7个移位分布中的5个覆盖(移位从 0到6)，因为我们假设随机数是独立于1的 Ran5()呼叫另一个，我们获得

p(x) = 5 / 35 = 1 / 7       for all x in [0, 6]

这意味着，给定来自ran5()的7个独立随机数，我们可以 计算一个在[0-6]范围内具有均匀概率的随机数。 实际上是ran5()概率 分布甚至不需要均匀，只要样本是均匀的 独立(所以每次试验的分布保持不变) 同样，这也适用于5和7之外的其他数字。

这为我们提供了以下python函数:

def rand_range_transform(rands):
    """
    returns a uniform random number in [0, len(rands) - 1]
    if all r in rands are independent random numbers from the same uniform distribution
    """
    return sum((x + i) for i, x in enumerate(rands)) % len(rands) # a single modulo outside the sum is enough in modulo arithmetic

可以这样使用:

rand5 = lambda : random.randrange(5)

def rand7():
    return rand_range_transform([rand5() for _ in range(7)])

如果我们调用rand7() 70000次，我们可以得到:

max: 6 min: 0 mean: 2.99711428571 std: 2.00194697049
0:  10019
1:  10016
2:  10071
3:  10044
4:  9775
5:  10042
6:  10033

这很好，尽管远非完美。事实上，我们的一个假设是 在这个实现中很可能是false:我们使用一个PRNG，因此，结果 的值依赖于上一个结果。

也就是说，使用一个真正随机的数字来源，输出也应该是 真正随机的。这个算法在任何情况下都终止。

但这是有代价的:我们需要为一个rand7()调用7次rand5() 调用。

(我剽窃了亚当·罗森菲尔德的答案，使其运行速度提高了7%左右。)

假设rand5()返回分布相等的{0,1,2,3,4}中的一个，目标是返回分布相等的{0,1,2,3,4,5,6}。

int rand7() {
  i = 5 * rand5() + rand5();
  max = 25;
  //i is uniform among {0 ... max-1}
  while(i < max%7) {
    //i is uniform among {0 ... (max%7 - 1)}
    i *= 5;
    i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
    max %= 7;
    max *= 5; //once again, i is uniform among {0 ... max-1}
  }
  return(i%7);
}

我们在跟踪这个循环在变量max中所能产生的最大值。如果到目前为止的结果在max%7和max-1之间，那么结果将均匀分布在该范围内。如果不是，则使用余数，余数是0到max%7-1之间的随机数，然后再次调用rand()来生成一个新的数字和一个新的max。然后我们重新开始。

编辑:在这个方程中，期望调用rand5()的次数是x:

x =  2     * 21/25
   + 3     *  4/25 * 14/20
   + 4     *  4/25 *  6/20 * 28/30
   + 5     *  4/25 *  6/20 *  2/30 * 7/10
   + 6     *  4/25 *  6/20 *  2/30 * 3/10 * 14/15
   + (6+x) *  4/25 *  6/20 *  2/30 * 3/10 *  1/15
x = about 2.21 calls to rand5()

只要没有剩下7种可能性，就再画一个随机数，将可能性数乘以5。在Perl中:

$num = 0;
$possibilities = 1;

sub rand7
{
  while( $possibilities < 7 )
  {
    $num = $num * 5 + int(rand(5));
    $possibilities *= 5;
  }
  my $result = $num % 7;
  $num = int( $num / 7 );
  $possibilities /= 7;
  return $result;
}

int getOneToSeven(){
    int added = 0;
    for(int i = 1; i<=7; i++){
        added += getOneToFive();
    }
    return (added)%7+1;
}

这里允许作业题吗?

这个函数进行粗略的“以5为基数”的数学运算，生成0到6之间的数字。

function rnd7() {
    do {
        r1 = rnd5() - 1;
        do {
            r2=rnd5() - 1;
        } while (r2 > 1);
        result = r2 * 5 + r1;
    } while (result > 6);
    return result + 1;
}