标签: collatz

灵感来自http://xkcd.com/710/这里是一个高尔夫代码.

挑战

给定大于0的正整数,打印出该数字的冰雹序列.

冰雹序列

有关更多详细信息,请参阅Wikipedia

• 如果数字是偶数,则除以2.
• 如果数字是奇数,则将其加倍并添加一个.

用生成的数字重复此操作,直到达到1.(如果在1之后继续,它将进入无限循环1 -> 4 -> 2 -> 1...)

有时代码是最好的解释方式,所以这里有一些来自维基百科

function collatz(n)
  show n
  if n > 1
    if n is odd
      call collatz(3n + 1)
    else
      call collatz(n / 2)

这段代码有效,但我正在增加额外的挑战.程序不能容易受到堆栈溢出的影响.所以它必须使用迭代或尾递归.

此外,如果它可以计算大数字并且语言尚未实现,则奖励积分.(或者如果使用固定长度的整数重新实现大数字支持)

测试用例

Number: 21
Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 …

我在Python3中编写了一个基本脚本来计算Collat​​z猜想.它采用正整数作为输入,并返回步骤的数字,直到序列下降到1.

我的脚本适用于任何小于2万亿的整数输入,但高于此阈值时输出太小.

举个例子,这里有一些输入,我的脚本的输出和实际的正确输出:

Integer Input          Script Output     Correct Output
   989,345,275,647        1,348             1,348 
 1,122,382,791,663        1,356             1,356 
 1,444,338,092,271        1,408             1,408 
 1,899,148,184,679        1,411             1,411 
 2,081,751,768,559          385             1,437 
 2,775,669,024,745          388             1,440 
 3,700,892,032,993          391             1,443 
 3,743,559,068,799          497             1,549 `

正确的输出值基于以下链接:http://www.ericr.nl/wondrous/delrecs.html

对于2万亿以上的输入,我的脚本输出总是比正确的输出少1,052,但我不知道是什么导致了这个.

谁能解释什么是错的,以及如何更新/修复脚本以使其适用于所有输入？我认为Python能够毫无问题地接受任意大数字...

谢谢!

# Python Code for the Collatz Conjecture
# Rules: Take any integer 'n' and assess:
# If integer is even, divide by 2 (n/2)
# If integer is odd, multiply by 3 and add 1 (3n+1)
# …

扰流警报:这与Project Euler的问题14有关.

以下代码需要大约15秒才能运行.我有一个在1s内运行的非递归Java解决方案.我想我应该能够更接近这个代码.

import Data.List

collatz a 1  = a
collatz a x
  | even x    = collatz (a + 1) (x `div` 2)
  | otherwise = collatz (a + 1) (3 * x + 1)

main = do
  print ((foldl1' max) . map (collatz 1) $ [1..1000000])

我已经分析过,+RHS -p并注意到分配的内存很大,并随着输入的增长而增长.对于n = 100,0001gb分配(!),分配n = 1,000,00013gb(!!).

然后再次-sstderr表明,尽管分配了大量字节,但总内存使用量为1mb,生产率为95%+,因此13gb可能是红鲱鱼.

我可以想到几个可能性:

1. 有些事情并不像它需要的那么严格.我已经发现了 foldl1',但也许我需要做更多的事情？是否有可能标记collatz 为严格(甚至有意义吗？

2. collatz不是尾部调用优化.我认为它应该是但不知道确认的方法.

3. 编译器没有做我认为应该进行的一些优化 - 例如collatz,任何一次只需要在内存中的两个结果(最大值和当前值)

有什么建议？

这几乎是一个重复的 …

为正整数集定义以下迭代序列:

n - > n/2(n是偶数)n - > 3n + 1(n是奇数)

使用上面的规则并从13开始,我们生成以下序列:

13 40 20 10 5 16 8 4 2 1可以看出,这个序列(从13开始,1完成)包含10个术语.虽然尚未证实(Collat​​z问题),但据认为所有起始数字都是1.

哪个起始编号低于一百万,产生最长的链？

注意:链条启动后,条款允许超过一百万.

我尝试使用bruteforce方法在C中编写解决方案.但是,似乎我的程序在尝试计算113383时失速.请指教:)

#include <stdio.h>
#define LIMIT 1000000

int iteration(int value)
{
 if(value%2==0)
  return (value/2);
 else
  return (3*value+1);
}

int count_iterations(int value)
{
 int count=1;
 //printf("%d\n", value);
 while(value!=1)
 {
  value=iteration(value);
  //printf("%d\n", value);
  count++;
 }
 return count;
}

int main()
{
 int iteration_count=0, max=0;
 int i,count;


 for (i=1; i<LIMIT; i++)
 {
  printf("Current iteration : %d\n", i);
  iteration_count=count_iterations(i);
  if (iteration_count>max)
   { …

我最近摆弄问题14的Euler project：该范围内数1..1_000_000的最长的在Collat​​z序列？

我知道必须记忆以获得合理时间的问题，并且以下Python代码使用该技术相对快速地返回答案（记忆到字典）：

#!/usr/bin/env python

L = 1_000_000
cllens={1:1}

cltz = lambda n: 3*n + 1 if n%2 else n//2

def cllen(n):
    if n not in cllens: cllens[n] = cllen(cltz(n)) + 1
    return cllens[n]

maxn=1
for i in range(1,L+1):
    ln=cllen(i)
    if (ln > cllens[maxn]): maxn=i

print(maxn)

（从这里改编；我更喜欢这个不使用的版本max，因为我可能想摆弄它以返回最长的 10 个序列等）。

我试图将其翻译为尽可能Raku保持语义上的接近：

#!/usr/bin/env perl6
use v6;

my $L=1_000_000;
my %cllens = (1 => 1); …

这是一个采访问题,似乎与Project Euler Problem 14有关

Collat​​z猜想说如果你做了以下几点

If n is even, replace n by n/2.
If n is odd, replace n by 3n+1.

你最终得到1.

例如, 5 -> 16 -> 8 -> 4 -> 2 -> 1

假设猜想为真,则每个数字都有一个链长:达到1所需的步数.(链长为1为0).

现在,给出自然数n,m和自然数k的问题,给出算法以找到1和n之间的所有数,使得这些数的链长<= k.还有一个限制,即任何这些数字的链必须只包括1到m之间的数字(即你不能超过m).

一种简单的方法是强制它,并将其与记忆结合起来.

采访者说有一个O(S)时间算法,其中S是我们需要输出的数字.

有谁知道它可能是什么？

我试图以懒惰的方式解决Project Euler Problem 14.不幸的是,我可能正在尝试做不可能的事情:创建一个既懒惰的懒惰序列,又以某种方式"向前看"尚未计算的值.

我写的测试正确性的非懒惰版本是:

(defn chain-length [num]
  (loop [len 1
         n  num]
(cond
  (= n 1) len 
  (odd? n) (recur (inc len) (+ 1 (* 3 n)))
  true     (recur (inc len) (/ n 2)))))

哪个有效,但确实很慢.当然我可以记住:

(def memoized-chain
   (memoize
     (fn [n]
       (cond
        (= n 1) 1 
         (odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
         true     (+ 1 (memoized-chain (/ n 2)))))))

然而,我真正想要做的是抓住我的痒,以理解延迟序列的限制,并编写如下函数:

(def lazy-chain
     (letfn [(chain [n] (lazy-seq
                         (cons (if (odd? n)
                                 (+ 1 (nth lazy-chain …

我在Scheme中写过Collat​​z猜想:

(define C
  (lambda (n)
    (cond
     ((eq? n 1) 1)
     ((even? n) (C (/ n 2)))
     (else (C (+ (* n 3) 1))))))

这是一个尾递归调用,但是当我调用时(C 121)我得到堆栈溢出:

guile> (trace C)
(C)
guile> (C 121)
[C 121]
[C 364]
[C 182]
[C 91]
[C 274]
[C 137]
[C 412]
[C 206]
[C 103]
[C 310]
[C 155]
[C 466]
[C 233]
[C 700]
[C 350]
[C 175]
[C 526]
[C 263]
[C 790]
[C 395]
[C 1186]
ERROR: Stack overflow
ABORT: (stack-overflow)

为什么正确的尾递归会导致溢出？如您所见,我使用Guile作为Scheme解释器(版本1.8.7).

我正在尝试在 Rust 中记忆递归 collat​​z 序列函数，但是我需要记忆值的哈希图来在单独的函数调用中保留其内容。有没有一种优雅的方法可以在 Rust 中做到这一点，或者我是否必须在 main 中声明 hashmap 并每次将其传递给函数？我相信每次调用该函数时，哈希映射都会被重新声明为空映射。这是我的代码：

fn collatz(n: int) -> int {
    let mut map = HashMap::<int, int>::new();
    if map.contains_key(&n) {return *map.get(&n);}
    if n == 1 { return 0; }
    map.insert(n, 
        match n % 2 {
            0 => { 1 + collatz(n/2) }
            _ => { 1 + collatz(n*3+1) }
        }
    );
    return *map.get(&n);
}

附带说明一下，为什么当我在 HashMap 中插入和取出项目时需要添加所有 & 和 * ？我这样做是因为编译器抱怨并添加它们修复了它，但我不确定为什么。我不能只按值传递吗？谢谢。

作为一项任务的另一个问题,我们被要求找到产生最长的连环标记序列的10个起始数字(n).(其中0 <n <10,000,000,000)我编写的代码有望实现这一点,但我估计需要整整11个小时来计算答案.

我注意到了一些小的优化,比如从最大到最小,因此添加到阵列的次数减少了,只计算在10,000,000,000/2 ^ 10(= 9765625)和10,000,000,000之间,因为必须有10个长度较长的序列,但是我看不到任何我能做的事情.有人可以帮忙吗？

相关代码序列搜索算法

long[][] longest = new long[2][10]; //terms/starting number
long max = 10000000000l; //10 billion

for(long i = max; i >= 9765625; i--) {
    long n = i;
    long count = 1; //terms in the sequence

    while(n > 1) {
        if((n & 1) == 0) n /= 2; //checks if the last bit is a 0
        else {
            n = (3*n + 1)/2;
            count++;
        }
        count++;
    }
    if(count > longest[0][9]) {
        longest = addToArray(count, …