Question:
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13) = 6. Notice that f(1) = 1. What's the next largest n such that f(n) = n?
As always, start with simple cases:
f(1) = 1,
f(2) = 1,
.......
f(9) = 1,
f(10) = 2, since 10 starts with 1, which we need to add.
f(11) = 4, since there are two 1's in 11 that we need to add.
f(12) = 5,
f(13) = 6,
....
f(19) = 12,
So between 12 and 19, we need to add 1 for each number because the second digit is one. Moreover, between 10 and 19, we add 10 1's from the second digit and one 1 from the last digit.
f(20) = 12,
f(21) = 13,
f(22) = 13,
.....
f(29) = 13,
So between 20 and 29, there is only one 1 from the last digit. Moreover, this is true for all subsequent intervals 30-39, 40-49, ......, 90-99. Consequently,
f(99) = 1 (between 1 and 9)
+ 1 (from the last digit in 11)
+ 10 (from the second digit in 10, 11, ......19)
+ 1 (in 31)
+ 1 (in 41)
+ ............
+ 1 (in 91)
= 10 (from second digit) + 10 (from first digit)
= 20.
In general, we can deduct
Lemma 1.
f(10^k - 1) = k * 10^(k-1)
for example,
f(9) = 1
f(99) = 2 * 10 = 20,
......
This is deducted from counting 1's in each digit for all number from 1 to 10^k -1, there are 10^(k-1) 1's in each of k digits. Actually, 1 appears in the last digit exactly once in every 10 consecutive numbers(like in 1, 11, 21, 31, ....) and so we have 10^k/10=10^(k-1) 1's contributed from last digit. Similarly, 1 appears 10 times in the second digit from last for every 100 consecutive numbers(like in 10-19, 110-119, 210-219, ...) and so we have 10 * (10^k/100) = 10^(k-1).
From this lemma, we can deduct
Lemma 2.
f(10^k) = k *10^(k-1) + 1.
The extra 1 is from the leading 1 in 10^k.
Recall the above process counting 1's between 10-99, we can deduct
Lemma 3.
f(m * 10^k) = m * f(10^k - 1) + 10^k = m * k * 10^(k - 1) + 10^k, for 1 < m < 9.
The second equality is using Lemma 1. This is just extending Lemma 1 to the cases where leading digits are bigger than 1.
The counting is just done by breaking the range between 1 and m * 10^k to two ranges, one is from 10^k to 2 * 10^k for leading 1's, and the rest. For example, f(5000) is breaking into 1-999, 1000-1999, 2000-2999, 3000-3999, and 4000-4999. Ignore the leading 1's, each range contributes f(10^k - 1). The leading 1's can only come from the second range 1000-1999, which has exactly 10^k leading 1's.
分享到:
相关推荐
shopid shopAllname fivescore scoreTaste scoreEnvironment scoreService avgPrice defaultReviewCount shopname branchName address phoneNo shopGroupId glat glng categoryName level2 level1 ...
idl代码与Matlab 辉光 Global airglOW模型,可以从Fortran 2003编译器中独立且轻松地进行访问。 可选提供脚本语言,包括: Python≥3.6 Matlab的 GNU八度≥4.2 IDL ...glat , glon , Q , Echar , Nb
接收 xyz 格式的点云,然后将其转换为具有纬度向量、经度向量、glat/glon 网格(使用 meshgrid)和 az(高度)矩阵的 MATLAB 样式的网格。 然后将这些保存到指定的输出 .mat 文件中。
它的构建允许任何人检查志愿者为数据库中或任何 GLON、GLAT 位置的任何主题(图像)创建的分类。 对于每个图像,您都可以看到原始志愿者绘图、聚类结果和该地区 SIMBAD 上的对象(这一点还没有完全完成)。 例如...
麦肯锡 组织 概述与基本框架gl.ppt
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
大型强子对撞机电源转换器设计与运行挑战
本文档提供了一套完整的STM32F411低功耗开发板资源,包含详细的原理图、PCB设计源文件、官方提供的示例程序以及必要的驱动程序。这些资料对于嵌入式系统开发者来说是宝贵的学习资源,特别适合那些希望深入了解STM32F411微控制器及其应用的学生、工程师和电子爱好者。文档旨在帮助用户快速上手STM32F411的开发工作,无论是进行学术研究、产品原型设计还是个人项目实践,都能从中获益。 关键词标签: STM32F411 低功耗 开发板 资料下载
该项目以发债企业作为研究对象,利用财务逻辑和技术手段对178个原始特征指标进行有效筛选,构建了基于多种机器学习算法的模型,对比后挑选LightGBM模型作为最终模型进行更精细化训练,最终模型关键预测指标均有比较好的效果。 使用说明 BondDefault文件为项目代码 基于机器学习的发债主体违约风险预测.pdf为pdf形式的项目文稿 基于机器学习的发债主体违约风险预测.pptx为ppt形式的项目展示 由于数据集太大,此处没有上传
Rain Birdt Simple To Set Timer (SST) 使用说明书
SITRANS LVL 200S, LVL 200E 振动式安全手册
麦肯锡-xx电信市场分析报告gl.ppt
基于matlab实现的三次样条插值法 求信号的包络线 源代码.rar
麦肯锡_xx大客户培训战略报告gl.ppt
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。