文档章节

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

BlackJoker
 BlackJoker
发布于 2015/10/14 11:15
字数 768
阅读 19
收藏 0
点赞 0
评论 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 ⋅ 0

Bad Coder(2011-01-04)

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

Pope怯懦懦地 ⋅ 2017/12/09 ⋅ 0

CodeMade:寻找开源物联网项目的优秀网站

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

达尔文 ⋅ 2016/12/06 ⋅ 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 ⋅ 0

Python中如何使用yield,对于庞大迭代的优化处理

一直困扰于yield的使用,今天看到一篇不错的解释,虽然都是英文,不过不要紧,可以跳开,直接看代码的部分就能懂 Improve Your Python: 'yield' and Generators Explained Posted on Apr 07...

青鸾之旅 ⋅ 2013/08/02 ⋅ 3

Leetcode 216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Ex......

ShutLove ⋅ 2017/11/27 ⋅ 0

并行算法库清单: 附各算法代码实例!

  【IT168 资讯】并行算法采用并行编程语言NESL实现,该语言是卡内基梅隆大学Scandal项目中开发的一种编程语言。对于每个算法,团队给出了一个简短的描述以及复杂性评估(就工作和深度而言)...

it168网站 ⋅ 2017/11/30 ⋅ 0

4Clojure hard题目-106

4Clojure是一个面向clojure初学者的在线答题网站,问题从易到难,一步步辅助初学者深入了解clojure Number Maze Difficulty: Hard Topics: numbers Given a pair of numbers, the start and...

池塘仙人 ⋅ 2012/11/20 ⋅ 0

A Visual, Intuitive Guide to Imaginary Numbers

maginary numbers always confused me. Like understanding e, most explanations fell into one of two categories: It’s a mathematical abstraction, and the equations work out. Deal ......

元谷 ⋅ 2015/11/04 ⋅ 0

Errai 4.0.0.CR2 发布,异步消息传递框架

Errai 4.0.0.CR2 发布了,该版本包含了大多数的 bug 修复以及一些 demo 的增强。下面是一些值得关注的更新: Fix Maven Parallel Build Issues Previously doing a parallel Maven build of...

局长 ⋅ 2017/03/08 ⋅ 3

没有更多内容

加载失败,请刷新页面

加载更多

下一页

C++内存映射文件居然是这样?!

内存映射文件大家都时不时听过,但它到底是个什么?赶紧来看看吧 内存映射文件到底是干嘛的呢?让我们先来思考下面几个问题: 如果您想读的内容大于系统分配的内存块怎么办?如果您想搜索的字...

柳猫 ⋅ 23分钟前 ⋅ 0

MySQL 数据库设计总结

规则1:一般情况可以选择MyISAM存储引擎,如果需要事务支持必须使用InnoDB存储引擎。 注意:MyISAM存储引擎 B-tree索引有一个很大的限制:参与一个索引的所有字段的长度之和不能超过1000字节...

OSC_cnhwTY ⋅ 今天 ⋅ 0

多线程(四)

线程池和Exector框架 什么是线程池? 降低资源的消耗 提高响应速度,任务:T1创建线程时间,T2任务执行时间,T3线程销毁时间,线程池没有或者减少T1和T3 提高线程的可管理性。 线程池要做些什...

这很耳东先生 ⋅ 今天 ⋅ 0

使用SpringMVC的@Validated注解验证

1、SpringMVC验证@Validated的使用 第一步:编写国际化消息资源文件 编写国际化消息资源ValidatedMessage.properties文件主要是用来显示错误的消息定制 [java] view plain copy edit.userna...

瑟青豆 ⋅ 今天 ⋅ 0

19.压缩工具gzip bzip2 xz

6月22日任务 6.1 压缩打包介绍 6.2 gzip压缩工具 6.3 bzip2压缩工具 6.4 xz压缩工具 6.1 压缩打包介绍: linux中常见的一些压缩文件 .zip .gz .bz2 .xz .tar .gz .tar .bz2 .tar.xz 建立一些文...

王鑫linux ⋅ 今天 ⋅ 0

6. Shell 函数 和 定向输出

Shell 常用函数 简洁:目前没怎么在Shell 脚本中使用过函数,哈哈,不过,以后可能会用。就像java8的函数式编程,以后获取会用吧,行吧,那咱们简单的看一下具体的使用 Shell函数格式 linux ...

AHUSKY ⋅ 今天 ⋅ 0

单片机软件定时器

之前写了一个软件定时器,发现不够优化,和友好,现在重写了 soft_timer.h #ifndef _SOFT_TIMER_H_#define _SOFT_TIMER_H_#include "sys.h"typedef void (*timer_callback_function)(vo...

猎人嘻嘻哈哈的 ⋅ 今天 ⋅ 0

好的资料搜说引擎

鸠摩搜书 简介:鸠摩搜书是一个电子书搜索引擎。它汇集了多个网盘和电子书平台的资源,真所谓大而全。而且它还支持筛选txt,pdf,mobi,epub、azw3格式文件。还显示来自不同网站的资源。对了,...

乔三爷 ⋅ 今天 ⋅ 0

Debian下安装PostgreSQL的表分区插件pg_pathman

先安装基础的编译环境 apt-get install build-essential libssl1.0-dev libkrb5-dev 将pg的bin目录加入环境变量,主要是要使用 pg_config export PATH=$PATH:/usr/lib/postgresql/10/bin 进......

玛雅牛 ⋅ 今天 ⋅ 0

inno安装

#define MyAppName "HoldChipEngin" #define MyAppVersion "1.0" #define MyAppPublisher "Hold Chip, Inc." #define MyAppURL "http://www.holdchip.com/" #define MyAppExeName "HoldChipE......

backtrackx ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部