文档章节

Project Euler Problem 387 - Harshad Numbers - 深度优先

BlackJoker
 BlackJoker
发布于 2015/10/14 11:15
字数 768
阅读 21
收藏 0

原题

A Harshad or Niven number is a number that is divisible by the sum of its digits. 201 is a Harshad number because it is divisible by 3 (the sum of its digits.) When we truncate the last digit from 201, we get 20, which is a Harshad number. When we truncate the last digit from 20, we get 2, which is also a Harshad number. Let's call a Harshad number that, while recursively truncating the last digit, always results in a Harshad number a right truncatable Harshad number.

Also: 201/3=67 which is prime. Let's call a Harshad number that, when divided by the sum of its digits, results in a prime a strong Harshad number.

Now take the number 2011 which is prime. When we truncate the last digit from it we get 201, a strong Harshad number that is also right truncatable. Let's call such primes strong, right truncatable Harshad primes.

You are given that the sum of the strong, right truncatable Harshad primes less than 10000 is 90619.

Find the sum of the strong, right truncatable Harshad primes less than 10<sup>14<sup>.

分析

Harshad Numbers(哈沙德数)

是可以在某个固定的进位制中,被其数位的数字之和整除的整数。

  • right truncatable Harshad number :循环截掉哈沙德数右边一个数字,新数字还是哈沙德数

  • strong Harshad number:如果哈沙德数与它的各位数字之和的比值是素数。

  • strong, right truncatable Harshad primes 是这样一类素数,去掉最后一个数字后,是一个strong Harshad number也是一个right truncatable Harshad number

穷举法有两条思路:

  • 思路一:基于素数搜索。 从11开始遍历下一个素数,判断它是不是满足条件的素数,把满足条件的素数相加直到10<sup>14</sup>;
  • 思路二:基数哈沙德数搜索。 从数字1 ~ 9开始(1 ~ 9都是哈沙德数),深度遍历搜索哈沙德数,在哈沙德数基础上递归搜索这个数末尾加上0~9之后是否素数,是否是哈沙德数,以此遍历下去。每次在末尾添加0 ~ 9 可以保证哈沙德数都是right truncatable的,无需而外运算。

实践证明,思路一不可行,10^14以内的素数不是短时间内可以遍历完的,而且对每个素数进行条件判断也比较耗时。思路二可行。

解题

基数哈沙德数深度优先搜索

static long N = (long) Math.pow(10, 14);
    /**
     * 按照 Truncatable HarshadNumber遍历:
     * @param n a Right Truncatable HarshadNumber
     * @param ds sum of digits of n
     * @param strong n is strong HarshadNumber
     * @return 以n为前缀的所有StrongRightTruncatableHarshad素数之和
     */
    public static long sumHarshadNumber(long n, int ds, boolean strong) {
        n = n * 10;
        if (n >= N) {
            return 0;
        }
        long sum = 0;
        for (int i = 0; i <= 9; i++) {
            n += i; // new n
            ds += i;// new ds
            if (strong && Util.isProbablePrime(n, 100)) {// new n is prime
                sum += n;
            }
            if (n % ds == 0) { // new n is a Right Truncatable HarshadNumber,recursive
                sum += sumHarshadNumber(n, ds, Util.isProbablePrime(n / ds, 100));
            }
            n -= i;// restore n
            ds -= i;// restore ds
        }
        return sum;
    }

其中,Util.isProbablePrime 如下:

    /**
     * 判断v是否可能是素数,是素数的概率为:1-1/2^certainty
     * @return
     */
    public static boolean isProbablePrime(long v, int certainty) {
        return BigInteger.valueOf(v).isProbablePrime(certainty);
    }

求和

    public static void main(String[] args) {
        long s = System.nanoTime();
        System.out.println(sumHarshadNumbes());
        System.out.println("Time consumed : " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - s) + " ms");
    }
    public static long sumHarshadNumbers() {
        long sum = 0;
        for (int i = 1; i < 9; i++) {
            sum += sumHarshadNumber(i, i, false);
        }
        return sum;
    }

输出

696067597313468
Time consumed : 168 ms

© 著作权归作者所有

共有 人打赏支持
BlackJoker
粉丝 1
博文 17
码字总数 9270
作品 0
深圳
高级程序员
Euler Project Problem 6

The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025......

长平狐
2012/10/16
51
0
Bad Coder(2011-01-04)

再优美的语言,如果你真的把它当作草稿来用,也还真是可以写出一些自惭形秽的-_-! 依然以奋斗在 Project Euler 界的我为例(这次的热情貌似久了一点)。 Problem 27 我们拿到的只是坐标,并非...

Pope怯懦懦地
2017/12/09
0
0
[Data Structures and Algorithms - 1] Introduction & Mathematics

References: 1. Stanford University CS97SI by Jaehyun Park 2. Introduction to Algorithms 3. Kuangbin's ACM Template 4. Data Structures by Dayou Liu 5. Euler's Totient Function Ge......

~yzhu
01/26
0
0
CodeMade:寻找开源物联网项目的优秀网站

大多数刚开始学习编程的用户在刚开始学习的前几个月都会遭遇相同的问题--根据书籍或网站来学习编程的基础知识,在成功打印出“HelloWorld”之后在自己编程之后总会遇到各种问题。遇到这些问题...

达尔文
2016/12/06
2.8K
5
数值计算系统--Euler

类似Matlab、Octave、Scilab的数值计算系统。 EULER is a program for quickly and interactively computing with real and complex numbers and matrices, or with intervals, in the style......

匿名
2011/04/18
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

CMD命令行:查看Windows操作系统的安装时间

电脑越用越卡,计划以后每两个月重新安装一次系统。 那,怎么查看自己系统的安装日期? 很简单的。cmd 中输入 systeminfo 命令,回车,等一会 …… 出来结果后,查找下面这一行,那就是系统的...

LivingInFHL
4分钟前
0
0
复习

10月19日任务 打印某行到某行之间的内容 sed转换大小写 sed在某一行最后添加一个数字 删除某行到最后一行 打印1到100行含某个字符串的行 一.打印某行到某行之间的内容 #sed -n '/\[abcfd\]/...

hhpuppy
5分钟前
0
0
精通Spring Boot——第十一篇:使用自定义配置

今天这篇文章给大家介绍自定义配置的两种方式 第一式: 使用@ConfigurationProperties,且看代码 package com.developlee.customconfig.config;import org.springframework.boot.context.p...

developlee的潇洒人生
11分钟前
0
0
python:pycharm启动出现异常:io.netty.channel.ChannelException.....

尝试用管理员权限启动终端, 输入: netsh winsock reset 重启电脑. 360的优化搞出来的幺蛾子........

Oh_really
20分钟前
0
0
设计模式学习与应用——策略模式

概念 策略模式定义了一系列的算法,并将每一个算法封装起来,而且使他们可以相互替换,让算法独立于使用它的客户而独立变化。 使用场景 1.在系统里面许多类,类之间区别仅在于方法行为,那么...

隔壁老余在这
24分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部