题目62：找出最小的立方数，使得它各位的排列中五个是立方数

欧拉计划

Cubic permutations

The cube, 41063625 can be permuted to produce two other cubes: 56623104 and 66430125 . In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

题目：

立方数 41063625 通过排列可以得到两个另外的立方数: 56623104 和 66430125 。 实际上 41063625 是最小的三个（不多不少）排列是立方数的立方数。

找出最小的立方数，其五个（不多不少）排列是立方数。

迷雾少年

怎么只跑了个3个的 。。除了题目给的。。 。。
1003003001
1030301000
1331000000

jerryxjr1220

5027 127035954683
7061 352045367981
7202 373559126408
8288 569310543872
8384 589323567104
0.298000097275

import time
start_1=time.time()
def changeNum(n):
    l=[x for x in str(n)]
    l.sort()
    return ''.join(l)
D,l,num1={},[],0
for i in range(1,10000):
    if changeNum(i**3) in D:
        D[changeNum(i**3)]+=1
    else:
        D[changeNum(i**3)]=0
for d in D:
    if D.get(d)==4:
        l.append(d)
num1=min(l)
for j in range(1,10000):
    if changeNum(j**3)==num1:
        print j,j**3
print time.time()-start_1

愤怒的大头菇

list1=[]
for i in range(10,10000):
    list1.append(i**3)
for i in range(len(list1)):
    temp = i+1
    count=1
    tmp = list(str(list1[i]))
    tmp.sort()
    while temp+1<len(list1):
        cmp=list(str(list1[temp]))
        cmp.sort()
        if tmp == cmp:
            count += 1
        temp += 1
    if count == 5:
        print(list1[i])
        break

结果：127035954683。差不多一分钟出结果，慢的不行

芒果加黄桃

# encoding:utf-8
# 找出最小的排列是五个立方数的数
from time import time
def euler062(N=1000):
    l_nums = []
    l_result = []
    n = 345
    while True:
        l_tmp = sorted([x for x in str(n ** 3)])
        l_result.append(l_tmp)
        l_nums.append(n)
        if l_result.count(l_tmp) == 5:
            for k in range(1, 6):
                 print(l_nums[l_result.index(l_tmp)])
                 l_nums.pop(l_result.index(l_tmp))
                 l_result.pop(l_result.index(l_tmp))  
            break
        n += 1 
if __name__ == '__main__':
    start = time() 
    euler062()
    print('cost %.6f sec' % (time() - start))

5027
7061
7202
8288
8384
cost 0.939648 sec

飘飞的白杨

from time import time
ttt = time()
def program62_1():
    n, s = 345, {}
    while True:
        temp = tuple(sorted(str(n**3)))
        if temp not in list(s.keys()):
            s[temp] = [n]
        elif len(s[temp]) == 4:
            print(s[temp]+[n])
            break
        else:
            s[temp] += [n]
        n += 1
def program62_2():
    n, s = 345, []
    while True:
        temp = sorted(str(n**3))
        s += [temp]
        if s.count(temp) == 5:
            print([i+345 for i in range(len(s)) if s[i] == temp])
            break
        n += 1
# program62_1()
program62_2()
print(time()-ttt)

najin

用的matlab
结果是：
127035954683
352045367981
373559126408
569310543872
589323567104
时间已过 4.986045 秒。
>>

jerryxjr1220

aardio编写：

import win.ui;
/*DSG{{*/
mainForm = win.form(text="aardio form";right=686;bottom=314;border="dialog frame";max=false)
mainForm.add(
button={cls="button";text="Calculate";left=91;top=207;right=599;bottom=268;z=2};
edit={cls="edit";left=88;top=67;right=602;bottom=193;edge=1;multiline=1;z=1};
static={cls="static";text="Euler 62";left=93;top=36;right=236;bottom=61;font=LOGFONT(h=-20);transparent=1;z=3}
)
/*}}*/

mainForm.button.oncommand = function(id,event){
        mainForm.button.text = "On Calculating..."
        stime = time.tick();
        mainForm.edit.print(win.invoke(
                function(mainForm){
                        var tab = {};
                        for i=1;10000 {
                                i3 = tostring(i**3);
                                var t = {};
                                for j=1;string.len(i3) {
                                        table.push(t,string.sub(i3,j,j));
                                }
                                table.sort(t);
                                var n = string.join(t,"");
                                var flag = true;
                                for k,v in tab {
                                        if k == n {
                                                table.push(v,i);
                                                flag = false;
                                                break;
                                        }
                                }
                                if flag {
                                        tab[n] = {i};
                                } else {
                                        if table.len(tab[n])==5 {
                                                return tab[n];
                                        }
                                }
                        }
                },mainForm
        ))
        mainForm.edit.print(time.tick()-stime,"ms");
        mainForm.button.text = "Calculate"
}

mainForm.enableDpiScaling();
mainForm.show();

return win.loopMessage();

[
    5027,
    7061,
    7202,
    8288,
    8384
]
1906        ms

hk1057

import time


def time_it():
        start=time.time()
        fun()
        end=time.time()
        print('cost %.6f Secs'%(end-start))


def sort_num(num):
        list_num=[x for x in str(num)]
        list_num.sort()
        return ''.join(list_num)


def fun():
        num=1
        list_num=[['1']]#[['1234',11,22,33]]6591002036752   6591002036833
        content=0
        index=0
        while True:
                if content:
                        break
                sorted_num=sort_num(num ** 3)
                for each in list_num:
                        if sorted_num in each[0]:
                                each.append(num)
                                if len(each) == 6:#五个排列是立方数
                                        content=1
                                        index=list_num.index(each)
                                break
                else:
                        list_num.append([sorted_num,num])
                num+=1
        print_list=list_num[index]
        print_list=print_list[1:]
        for each in print_list:
                print(each,each**3,sort_num(each**3))
       
               
if __name__=='__main__':
        time_it()
'''
5027 127035954683 012334556789
7061 352045367981 012334556789
7202 373559126408 012334556789
8288 569310543872 012334556789
8384 589323567104 012334556789
cost 1.165871 Secs
'''

哧哧炽

najin 发表于 2017-10-2 20:05
用的matlab
结果是：
127035954683

想知道用MATLAB的代码，如果可以的话可以透露一下吗？非常感谢！

哧哧炽

想知道有没有用MATLAB编码的啊？

王小召

自己代码太垃圾, 转不过来了！只知道题目要求只有五个，所以都要遍历一遍吧。。但是看楼上代码，貌似碰到5直接中断答案也是一样的不变；

结果是：[(5027, 127035954683), (7061, 352045367981), (7202, 373559126408), (8288, 569310543872), (8384, 589323567104)]
用时：22.0429413 秒

import time


def Func1():
    bool_range = [0] * 100000
    for i, j in enumerate(bool_range):
        if not j:
            start_range = i ** 3
            length = len(str(start_range))
            start = i + 1
            result = [(i, i ** 3)]
            while len(str(start ** 3)) == length:
                if sorted(list(str(start_range))) == sorted(list(str(start ** 3))):
                    result.append((start, start**3))
                    bool_range[start] = 1
                start += 1
            if len(result) == 5:
                return result


print("结果是：{}\n用时：{} 秒".format(Func1(), time.process_time()))

永恒的蓝色梦想

C++ 3ms

#include<iostream>
#include<limits>
#include<unordered_map>



size_t hash_permutation(unsigned long long n) {
    constexpr unsigned long long add[] = { 1ull, 1ull << 5, 1ull << 10, 1ull << 15, 1ull << 20, 1ull << 25, 1ull << 30, 1ull << 35, 1ull << 40, 1ull << 45 };
    constexpr unsigned short ENLARGE = (unsigned long long)(-1) / (0b10100ull << (9 * 5));

    unsigned long long t, result = 0;


    while (n) {
        t = n;
        n /= 10;
        result += add[t - n * 10];
    }


    return result * ENLARGE;
}



struct MapVal {
    unsigned long long min;
    unsigned char count = 0;
};



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    unordered_map<size_t, MapVal> counter;
    unsigned long long n, cube_of_n;
    MapVal* ptr;


    for (n = 1; n < 10000; n++) {
        cube_of_n = n * n * n;
        ptr = &counter[hash_permutation(cube_of_n)];

        if (!(ptr->count)) {
            ptr->min = cube_of_n;
        }

        ptr->count++;
    }


    n = numeric_limits<unsigned long long>::max();

    for (auto& i : counter) {
        if (i.second.count == 5) {
            if (i.second.min < n) {
                n = i.second.min;
            }
        }
    }


    cout << n << endl;
    return 0;
}

ft215378

jerryxjr1220 发表于 2016-10-9 23:25

能不能麻烦大神解释一下 我看不明白

guosl

/*
答案：127035954683
耗时：0.776675秒（单核）
      0.10129秒（六核）
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <omp.h>
using namespace std;

const int nSteps = 10;

int main(void)
{
  double t = omp_get_wtime();
  int k = 406;
  int nR = 0x7fffffff;
  bool bContinue = true;
#pragma omp parallel shared(k,bContinue) reduction(min:nR)
  while (bContinue)
  {
    int k2 = 0;
#pragma omp critical
    {
      k2 = k;
      k += nSteps;
    }
    for (int k1 = k2; bContinue && k1 < k2 + nSteps; ++k1)
    {
      long long lk = k1;
      lk = lk * lk * lk;
      char str[20];
      sprintf_s(str, "%lld", lk);
      int nL = strnlen_s(str, 20);
      sort(str, str + nL);
      int nCount = 1;
      int j = k1 + 1;
      while (bContinue)
      {
        long long lj = j;
        lj = lj * lj * lj;
        char strj[20];
        sprintf_s(strj, "%lld", lj);
        int nLj = strnlen_s(strj, 20);
        if (nLj > nL)
          break;
        sort(strj, strj + nLj);
        if (strcmp(str, strj) == 0)
          ++nCount;
        ++j;
      }
      if (nCount == 5)
      {
        nR = min(k1, nR);
        bContinue = false;
#pragma omp flush(bContinue)
        break;
      }
    }
  }
  t = omp_get_wtime() - t;
  cout << (long long)nR * nR * nR << endl << t << endl;
  return 0;
}

B1tetheDust

import time as t

start = t.perf_counter()


class P62:

    def __init__(self, test_range):
        self.test_range = test_range
        self.cubic_pool = [i ** 3 for i in range(200, test_range)]
        self.bool_num = [True] * (test_range - 345)
        self.count = 1
        self.num_list = []
        self.find_nums()

    @staticmethod
    def is_permutable(num_1, num_2):
        str_num_1, str_num_2 = str(num_1), str(num_2)
        if len(str_num_1) != len(str_num_2):
            return False
        for each_digit in str_num_1:
            if each_digit not in str_num_2:
                return False
            else:
                str_num_2 = str_num_2.replace(each_digit, '', 1)
        return True

    def check_num(self, num_1):
        test_num = num_1 + 1
        while test_num < self.test_range:
            if self.bool_num[test_num - 345] and \
                    self.is_permutable(self.cubic_pool[num_1 - 200], self.cubic_pool[test_num - 200]):
                self.count += 1
                self.num_list.append(test_num)
                self.bool_num[test_num - 345] = False
            test_num += 1

    def find_nums(self):
        for num0 in range(345, self.test_range):
            if self.bool_num[num0 - 345]:
                self.num_list = [num0]
                self.count = 1
                self.check_num(num0)
                if self.count == 5:
                    print(self.num_list)
                    print([self.cubic_pool[j - 200] for j in self.num_list])
                    break


res = P62(10000)
print("It costs %f s" % (t.perf_counter() - start))

[5027, 7061, 7202, 8288, 8384]
[127035954683, 352045367981, 373559126408, 569310543872, 589323567104]
It costs 23.116533 s