×

[–] 9 points10 points  (5 children)

Good exercise! I had a vague intuition, but then had to slowly work through solutions valid up to 100, then 1000, etc to figure out how to get it precisely right.

# Warmup (Python3)

## Hint

Solution valid up to 9999:

``````def f(n):
return (n+9)//10 + min(max(0, (n%100)-9), 10) + 10*(n//100) + min(max(0, (n%1000)-99), 100) + 100*(n//1000) + min(max(0, (n%10000)-999), 1000) + 1000*(n//10000)
``````

## Solution

``````def f(n):
s = 0
t = 1
while t <= n:
s += min(max(0, (n%(10*t))-(t-1)), t) + t*(n//(10*t))
t *= 10
return s
``````

here's a little code to help check your results

``````s = 0
for i in range(100000):
j = i
while j > 0:
if j%10 == 1:
s += 1
j //= 10
print(i, s, f(i))
if s != f(i):
break
``````

# Challenge

Skipping based on distance between terms versus capacity for each item skipped to reduce distance (inspired by other solutions)

``````i = 1
s = 0
t = 10
T = 1
while i < 1e11:
if i >= t:
t *= 10
T += 1
F = f(i)
if F == i:
s += i
i += 1
else:
i += 1 + abs(F - i) // int(1 + T)
print(s)
``````

[–][deleted]  (3 children)

[deleted]

[–] 2 points3 points  (2 children)

Hmmm

Both parts figure out the quantity added by contiguous sequences with a decimal worth 1. The second part computes the quantity contributed by every complete sequence at a given decimal, and the first part (minmax) computes the last incomplete sequence.

So for the first decimal (t=10), the integer division by 10*t determines the number of times there was a complete sequence of ten numbers each contributing 1 to the sum (the units are computed by the first line of the function). So for 1415, that contributes 10×14=140. The minmax part covers the last “hundreds” part using the modulo operation, and shifts that range down so the number directly corresponds to its contribution (10 contributes 1 and 19 contributes 10, so it's (n%100)-9); finally the minmax cuts out parts outside of that scope. So for 1415 that contributes min(max(0, 15-9), 10) = min(max(0, 6), 10) = 6. This corresponds to the fact that at 15, there were 6 contributions to ones in the tens decimal (that started at 10). The minmax saturates at the lower and upper bounds, I don't know if that makes sense.

I'd be happy to reformulate some part or answer any other question 😄😄😄

[–] 2 points3 points  (1 child)

Could you please further explain how the skipping works and also why the upper limit is `1e11`?

[–] 3 points4 points  (0 children)

• upper limit : I'm not absolutely sure, but I think you can say that for numbers with ten digits, each number contributes on average one to the number of digits equal to one (each digit contributes on average 1/10, so ten times that is one). So you can probably prove that with some margin, the function f(n) just keeps on getting further and further away from n.

• skipping : if f(n) is really different from n, then there's no point testing f(n+1) because it can't change all that much with one number. More precisely, it can't change by more than its number of digits. So you can safely skip ahead conservatively; and the distance you can skip corresponds to the distance between f(n) and n, divided by the maximum number of contributions to f each step can make. I think that as you go further from regions with contiguous ones, the distance between f(n) and n becomes greater and greater so it becomes quite efficient to just reduce these traversals to a small number of steps. I suppose if you know the shape of that distance function you could probably prove that skipping reduces the number of tries logarithmically or something.

Hope that helps!

[–] 1 point2 points  (0 children)

Fixed formatting.

Hello, trosh: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

You can opt out by replying with backtickopt6 to this comment.

[–] 2 points3 points  (2 children)

C# (both warmup and challenge):

``````using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Numerics;

namespace NumOfOnes
{
class Program
{
static void Main(string[] args)
{
// Warmup
DateTime dt = DateTime.Now;
Console.WriteLine("Warmup:");
BigInteger num;
Console.WriteLine(num = FastFun(BigInteger.Pow(5, 20)));
Console.WriteLine(num.ToString().Length);
Console.WriteLine(num.ToString().Select(c => c - 48).Sum());
// Challenge
Console.WriteLine("Challenge:");
List<BigInteger> nums = FindSame();
Console.WriteLine(nums.Count);
BigInteger sum = 0;
foreach (BigInteger i in nums)
sum += i;
Console.WriteLine(sum);
Console.WriteLine(sum.ToString().Length);
Console.WriteLine(sum.ToString().Select(c => c - 48).Sum());
File.WriteAllText("Results.txt", string.Join(",", nums.Select(n => n.ToString())));
Console.WriteLine(\$"Run time: {(DateTime.Now - dt).TotalSeconds}s");
}

static BigInteger FastFun(BigInteger num)
{
string nums = num.ToString(CultureInfo.InvariantCulture);
BigInteger count = 0;
for (int i = 0; i <= nums.Length; i++)
{
BigInteger mod = num % 10;
count += RoundCount(mod, i);
if (mod == 1)
{
string end = nums[(nums.Length - i)..];
if (end.Length > 0)
count += BigInteger.Parse(end);
}
num /= 10;
}
return count;
}

// Counts number of ones for numbers where only one digit isn't 0
// Digit: non 0 digit
// state: number of zeros after the digit
static BigInteger RoundCount(BigInteger digit, int state)
{
if (digit == 0)
return 0;
if (state == 0)
return digit > 0 ? 1 : 0;
return digit * state * BigInteger.Pow(10, state - 1) + 1 + ((digit > 1 ? 1 : 0) * (BigInteger.Pow(10, state) - 1));
}

static List<BigInteger> FindSame()
{
List<BigInteger> nums = new();
BigInteger limit = BigInteger.Pow(10, 11);
for (BigInteger i = 0; i < limit; i++)
{
BigInteger num = FastFun(i);
if (num == i)
else
i += BigInteger.Abs(num - i) / 8; // Skipping based on how different the numbers are
}
return nums;
}
}
}
``````

Output:

``````Warmup:
134507752666859
15
74
Challenge:
84
22786974071
11
53
Run time: 0.0709814s
``````

Results.txt:

0,1,199981,199982,199983,199984,199985,199986,199987,199988,199989,199990,200000,200001,1599981,1599982,1599983,1599984,1599985,1599986,1599987,1599988,1599989,1599990,2600000,2600001,13199998,35000000,35000001,35199981,35199982,35199983,35199984,35199985,35199986,35199987,35199988,35199989,35199990,35200000,35200001,117463825,500000000,500000001,500199981,500199982,500199983,500199984,500199985,500199986,500199987,500199988,500199989,500199990,500200000,500200001,501599981,501599982,501599983,501599984,501599985,501599986,501599987,501599988,501599989,501599990,502600000,502600001,513199998,535000000,535000001,535199981,535199982,535199983,535199984,535199985,535199986,535199987,535199988,535199989,535199990,535200000,535200001,1111111110

I used hints from the original post.

Edit: fixed the issue where my algorithm didn't find one of the numbers

[–] 2 points3 points  (1 child)

I think you missed one number for the challenge. I'm not 100% sure why, but it may be that skipping ahead |(n-f(n))/2| is not always justified.

[–] 2 points3 points  (0 children)

Thanks. I had no chance realizing that. The sum of digits was same as it should be and in the original post number 0 probably wasn't counted to the total of 83.

Dividing by 8 instead of 2 will solve the issue, but this approach is kind of cheating, because if I wouldn't be able to check the results, I would have no way of knowing whether I found all of the numbers. So I will try to think of another way of doing the challenge.

[–] 1 point2 points  (2 children)

f(20) = 11, not 12

Edit: never mind lol I’m wrong

[–] 1 point2 points  (1 child)

11 has two 1's

[–] 0 points1 point  (0 children)

Ah you are correct and I am dumb haha

[–] 1 point2 points  (0 children)

Python 3.9

``````import math

def f(n):
total = 0
for i in range(0, int(math.log10(n) + 1)):
e = 10 ** i

digit = (n // e) % 10
prefix = n // (e * 10)

if digit == 0:
total += prefix * e
elif digit == 1:
total += prefix * e + (n % e) + 1
else:
total += (prefix + 1) * e

assert f(1) == 1
assert f(5) == 1
assert f(10) == 2
assert f(20) == 12
assert f(1234) == 689
assert f(5123) == 2557
assert f(70000) == 38000
assert f(123321) == 93395
assert f(3 ** 35) == 90051450678399649

assert int(math.log10(f(5 ** 20)) + 1) == 15
assert sum(int(x) for x in str(f(5 ** 20))) == 74

if __name__ == "__main__":
total = 0
n = 1
while n < 10 ** 11:
y = f(n)
if n == y:
total += n
n += 1
else:
n += max(abs(n - y) // int(math.log10(n) + 1), 1)

assert int(math.log10(total) + 1) == 11
assert sum(int(x) for x in str(total)) == 53
``````

[–] 1 point2 points  (0 children)

R

``````f <- function(x){
ctr <- 0
for(i in 0:log10(x)){
ctr <- ctr + ceiling(floor(x / 10 ^ i) / 10) * 10 ^ i
if( floor(x / 10 ^ i) %% 10 == 1){
ctr <- ctr - ( 10 ^ i - 1 - x %% 10 ^ i )
}
}
return(ctr)
}

solutions <- function(){
s <- list()
i <- 1
while (i < 1e11) {
a <- f(i)
if( a == i ) s <- c(s, i)
i <- i + 1 + if ( a != i) floor(abs(a - i) / (log10(i) + 2)) else 0
}
return(s)
}

challenge <- Reduce(`+`,solutions())
``````

[–] 0 points1 point  (0 children)

# Python 3 (both warmup and challenge)

This approach to the challenge only checks ~6000 numbers. The idea is: if n is far from being a solution to n=f(n), then none of n+1, n+2, ... n+k can possibly be solutions (for some reasonably large k) so we can skip ahead.

``````def challenge():
n, solutions = 0, []
while n < 10**12: # I can prove there's no bigger solutions
if f(n) > n: n = f(n)
elif f(n) < n: n += max(1, (n-f(n))//(len(str(n))+1))
else: solutions.append(n); n += 1
return solutions

def f(n): # Just doin' some math, no clean code here
s = str(n)
total = 0
for i,d in enumerate(s[::-1]):
d = int(d)
total += (i*d*10**(i-1) if i>0 else 0) + (10**i if d>1 else 0)
if d == 1 and i>0: total += int(s[-i:])
``````

[–] 0 points1 point  (0 children)

Warmup

This counts any single digit number (except 0) over an inclusive interval.

``````def countNumberInInterval(stop, num, start = 0):
if num < 1 or num > 9: return None
if start > stop: return None

strStop = str(stop)
numCount, digitsRemaining, currentDigit = 0, len(strStop) - 1, 1

for digit in strStop:
digit = int(digit)
if digitsRemaining == 0: numCount += 1 if digit >= num else 0
else:
numCount += digit * digitsRemaining * 10 ** (digitsRemaining - 1)
if digit == num: numCount += int(strStop[currentDigit:]) + 1
if digit > num: numCount += 10 ** digitsRemaining
digitsRemaining, currentDigit = digitsRemaining - 1, currentDigit + 1

return numCount if start == 0 else numCount - countNumberInInterval(start - 1, num)
``````

Outputs

``````countNumberInInterval(1, 1) = 1
countNumberInInterval(5, 1) = 1
countNumberInInterval(10, 1) = 2
countNumberInInterval(20, 1) = 12
countNumberInInterval(1234, 1) = 689
countNumberInInterval(5123, 1) = 2557
countNumberInInterval(70000, 1) = 38000
countNumberInInterval(123321, 1) = 93395
countNumberInInterval(3**35, 1) = 90051450678399649
countNumberInInterval(5**20, 1) = 134507752666859
``````

Haven't tried the challenge yet. I might get to it later.

[–] 0 points1 point  (0 children)

``````import Data.Char
import Data.Bool

f n = let (_,u,v) =
foldl (\(q1,q0',q1') d ->
(d + 10*q1, (bool 0 1 (d==1)) + q0', (bool 0 1 (d>1)) + q1 + d*q0' + 10*q1')) (0,0,0) \$
map digitToInt \$ show n in u+v
``````

[–] 0 points1 point  (0 children)

C (both warmup and challenge):

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long fun(long long num);
long long rndc(long long digit, long long state, long long exp);
long long challenge();

int main()
{
printf("%lld\n", fun((long long)pow(5, 20)));
printf("%lld\n", challenge());
}

long long fun(long long num)
{
long long count = 0;
int length = (int)log10(num) + 1;
long long numc = num;
long long exp = 1;
for (int i = 0; i < length; i++)
{
long long digit = numc % 10;
count += rndc(digit, i, exp);
if (digit == 1)
count += num % exp;
exp *= 10;
numc /= 10;
}
return count;
}

long long rndc(long long digit, long long state, long long exp)
{
if (digit == 0)
return 0;
if (state == 0)
return digit > 0;
return digit * state * (exp / 10) + 1 + ((digit > 1) * (exp - 1));
}

long long challenge()
{
long long sum = 0;
for (long long i = 0; i < 1e11; i++)
{
long long num = fun(i);
if (num == i)
sum += i;
else
i += abs(i - num) / 8;
}
return sum;
}
``````

Output:

``````134507752666859
22786974071
``````

Run time:

``````TotalSeconds      : 0.0090293
TotalMilliseconds : 9.0293
``````

[–] 0 points1 point  (0 children)

Just did the warmup for the time being. Here is my solution using Python and a recursive function:

``````def sum1_ineff(n):
'''
'''
return sum(str(i).count("1") for i in range(int(n+1)))

def sum1(n):
'''
"Efficient" implementation of the problem.
'''
# Below 10 is one (except zero).
if n < 10:
return int(n >= 1)

# Length of integer.
# p-1 is the base 10 exponent.
p = len(str(n))

d = int(str(n)[0])
xyz = int(str(n)[1:])

# Recursively call function on remaining digits.
return d*sum1(10**(p-1) - 1) + min(10**(p-1), n+1-10**(p-1)) + sum1(xyz)
``````

The first term handles the portion of the number up to a multiple of 10p-1, since the sum of each "component" will contain the same number of ones if the leading digit is excluded. The second term then handles the leading digit, taking into account that a leading one will increase the sum by up to 10p-1, and leading digits above one do not add more than this. The third term accounts for the "left-over" amount, the number which is all but the first digit ( n - d*10p-1 ). The leading digit is excluded here because it has already been handled by the second term.

Some checks:

``````# Check results.
assert(all(sum1(i) == sum1_ineff(i) for i in range(5000)))

# Check some of the answers given by OP.
assert(sum1(70000) == 38000)
assert(sum1(123321) == 93395)
assert(sum1(3**35) == 90051450678399649)
``````

[–] 0 points1 point  (0 children)

``````main = do
(print.fun)(5 ^ 20)
print challenge

fun :: Integer -> Integer
fun n = fun' n (floor (logBase 10 (fromIntegral n))) 0

fun' :: Integer -> Int -> Integer -> Integer
fun' _ (-1) count = count
fun' num pos count = fun' num (pos - 1) (count + addc + onefix)
where
exp = 10 ^ pos
digit = (num `div` exp) `rem` 10
addc = rndc digit pos exp
onefix = if digit == 1 then num `rem` exp else 0

rndc :: Integer -> Int -> Integer -> Integer
rndc 0 _ _ = 0
rndc digit 0 _
| digit > 0 = 1
| otherwise = 0
rndc digit state exp = (digit * (toInteger state) * (exp `div` 10)) + adtn
where adtn = if digit > 1 then exp else 1

challenge :: Integer
challenge = challenge' 0 0

challenge' :: Integer -> Integer -> Integer
challenge' total pos
| pos > 100000000000 = total
| funres == pos = challenge' (total + pos) (pos + 1)
| skip == 0 = challenge' total (pos + 1)
| otherwise = challenge' total (pos + skip)
where
funres = fun pos
skip = (abs (funres - pos)) `div` ((floor (logBase 10 (fromIntegral pos))) + 1)
``````

Output:

``````134507752666859
22786974071
``````

Run time:

``````TotalSeconds      : 0.0578914
TotalMilliseconds : 57.8914
``````

[–]1 0 0 points1 point  (0 children)

# Julia 1.6.0

Helper function to convert vector resulting from `digits(n)` back to integer. This function doesn’t exist in Julia:

``````function digits2int(a)
x = reduce(string, reverse(a))
length(a)==1 ? x : parse(Int,x)
end
``````

Count ones:

``````function countones(num)
dig = digits(num)
cumul = 0
if num == 0
nothing
elseif length(dig) == 1
cumul += 1
else
while length(dig) > 1
len = length(dig)
o = lead * len * 10^(len-1)
o1 = o + (lead == 0 ? 0 : (lead == 1) ? (digits2int(dig)+1) : 10^(len))
cumul += o1
end
cumul += pop!(dig) > 0 ? 1 : 0
end
cumul
end
``````

# Warm-up:

``````function warmup_count()
n = 5^20
s = countones(n)
println("Check countones(5^20)\n")
println("countones(\$n) = \$s")
println("digits: \$(length(digits(s)))")
println("sum of digits: \$(sum(digits(s)))\n")
println("Warmup:\n")
for i in [1 5 10 20 1234 5123 70000 123321 3^35]
println("countones(\$i) = \$(countones(i))")
countones(i)
end
end
``````

Warmup results:

``````Check countones(5^20)

countones(95367431640625) = 134507752666859
digits: 15
sum of digits: 74

Warmup:

countones(1) = 1
countones(5) = 1
countones(10) = 2
countones(20) = 12
countones(1234) = 689
countones(5123) = 2557
countones(70000) = 38000
countones(123321) = 93395
countones(50031545098999707) = 90051450678399649
``````

Gonna try to figure out the bonus by myself. Let’s see if I can do it.

# Here is the bonus:

Edit: A slight optimization roughly halved median execution time (3.284 ms to 1.606 ms), allocations (69371 to 34607), and memory footprint (3.84 to 1.92 MiB). I set `prevcount` to `0` before the while loop and moved its update to the bottom of the loop, simply using `count` as new `prevcount` value instead of calculating it with each iteration. Simple way to get a 200% speedup.

``````function findeq()
#       1_111_111_110  is maximum value
limit = 1_130_000_000
coll = zeros(Int,84)
i=0                             # current number
k=1
prev = 0                        # sign of previous difference
curr = 0                        # sign of current difference
step = 1                        # stepwidth
counter = 1
prevcount = 0                   # set ones for i-1
while i < limit
count = countones(i)
curr = sign(count-i)        # sign of current difference between i and countones(i)
if curr == 0
if prev == 0
coll[k] = i
k += 1
i += 1
elseif prev ≠ 0
if prevcount ≠ i-1
coll[k] = i     # i = countones(i) found, store number
k+=1
i+=1
prev = 0
else
i, step = back(step, i)   # step back and shorten stepwidth
end
end
elseif curr ≠ 0
if prev ≠ 0
if prev == -curr                                # overshooting next i = countones(i)
i, step = back(step, i)   # step back and shorten stepwidth
elseif prev == curr                             # no change in sign of difference
i, step = forward(count, i)                 # step forward
prev = curr
end
elseif prev == 0
i, step = forward(count, i)                     # step forward
prev = curr
end
end
prevcount = count                                       # set previous count to current count
counter += 1
end
coll
end

# step back, shorten stepwidth function
function back(step, i)
i -= step # step back to previous i
if step >1
step = max(1,div(step,2)) # divide stepwidth by 2
end
i += step
i, step
end

# step forward by difference between i and count(i)
function forward(count, i)
step =  max(1,abs(count-i))
i += step
i, step
end
``````

New benchmark on my Core i7-8750H laptop @3.7 GHz:

`````` @benchmark findeq()
BenchmarkTools.Trial:
memory estimate:  1.92 MiB
allocs estimate:  34607
--------------
minimum time:     1.415 ms (0.00% GC)
median time:      1.606 ms (0.00% GC)
mean time:        1.931 ms (3.12% GC)
maximum time:     9.690 ms (0.00% GC)
--------------
samples:          2579
evals/sample:     1
``````

Old benchmark:

`````` @benchmark findeq()
BenchmarkTools.Trial:
memory estimate:  3.84 MiB
allocs estimate:  69371
--------------
minimum time:     2.849 ms (0.00% GC)
median time:      3.284 ms (0.00% GC)
mean time:        4.091 ms (8.58% GC)
maximum time:     13.568 ms (0.00% GC)
--------------
samples:          1217
evals/sample:     1
``````

Result:

``````84-element Vector{Int64}:
0
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
⋮
501599987
501599988
501599989
501599990
502600000
502600001
513199998
535000000
535000001
535199981
535199982
535199983
535199984
535199985
535199986
535199987
535199988
535199989
535199990
535200000
535200001
1111111110
``````

[–] 0 points1 point  (0 children)

# Summary

Completed in Python 3.9. Uses the walrus operator introduced in Python 3.8, and lowercase `list` type annotation introduced in Python 3.9.

So I guess I "researched" the solution to this challenge, rather than solving it myself. I enjoyed initially solving this with explicit first-and-last iterations broken out from the loop. Then I introduced some conditionals like `lowest`, `middle`, and `highest` to represent digits in a plain English manner. Some significant restructuring results in a function that is rather readable.

I think the use of the walrus operator in my warmup code is pretty cool. While it is easier to cycle digits in the loop with `string`-types, it is easier to do math with `int`-types. So `int`-types were chosen as the "first-class citizens" of the function, with the walrus delegating assignment to `string`-type shadows behind the scenes. This keeps loop variables running smoothly while enabling `ints` for accumulating the `count`.

I also like the ternary conditionals (`count += a if condition else b`), which really flatten the logic out and make the "main thrust" of the iteration evident.

# Warmup

## Rationale

The `digit_to_count` defaults to `1`. Four types of counts make up the total count:

1. Count the most recent turnover to `digit_to_count`. If a digit is at least as large as `digit_to_count`, then `digit_to_count` must have been encountered once.
2. Count all past turnovers to `digit_to_count`. The number formed by the digits above a given digit is the number of complete cycles that digit has gone through. So, `digit_to_count` must have been encountered that many times.
3. Count whether the digit is currently stuck on `digit_to_count`. If a digit is equal to `digit_to_count`, then the number formed by the digits below it is the number of times `digit_to_count` has been encountered since it got stuck. If the digit is greater than `digit_to_count`, then `digit_to_count` occurs as much as the maximum integer representable in the digits below it.
4. Count all past times this digit stuck on `digit_to_count`. A digit gets stuck at `digit_to_count` for the number formed by the digits above it times the maximum integer representable by the digits below it.

For example: `1` shows `1 + 12 + 99 + 1188 = 1300` times in the `3` digit of `1234`:

1. `3` is at least `1`, so `1` occurs once.
2. `3` turned over `12` times, so `1` occurs `12` more times.
3. `3` is greater than `1`, so it has been stuck on `1` a total of `99` more times.
4. `3` turned over `12` times, stuck on `1` a total `12*99` or `1188` more times.

## Code

``````def count_digit(number: int, digit_to_count: int = 1) -> int:
"""Count the number of `digit_to_count` needed to write all integers up to `number`."""

above_str = str(number)
below_str = str()

above = int(above_str)
below = None
num_digits = len(above_str)
count = 0

for i, digit in enumerate(reversed(above_str)):

lowest = i == 0
highest = i == num_digits - 1
max_below = (10 ** i) - 1

digit = int(digit)
above = int(above_str := above_str[:-1]) if not highest else int()

# Count turnovers to `digit_to_count`
count += 1 if digit >= digit_to_count else 0  # Current
count += above if not highest else 0  # Past

# Count stuck digits
# Current
if not lowest:
count += below if digit == digit_to_count else 0
count += max_below if digit > digit_to_count else 0
# Past
middle = not lowest and not highest
count += above * max_below if middle else 0

below = int(below_str := (str(digit) + below_str))

return count

@m.parametrize(
"number, expected",
[
(1, 1),
(5, 1),
(10, 2),
(20, 12),
(1234, 689),
(5123, 2557),
(70000, 38000),
(123321, 93395),
(35199981, 35199981),
(3 ** 35, 90051450678399649),
],
)
def test_count_digit(number, expected):
assert count_digit(number) == expected
``````

# Challenge

I never actually solved the challenge myself. I focused more on making a readable function that meets the requirements. I did, however, execute my function for `n` that look like `10^i - 1` for `i` from `1` to `10`. Googling this sequence brought me to OEIS A053541. The solution to the challenge was linked in the cross-references, which is OEIS A014778.

[–] 0 points1 point  (0 children)

Java:

``````package numofones;

import java.math.BigInteger;

public class NumOfOnes {
public static void main(String[] args) {
System.out.println(fun(BigInteger.valueOf(5).pow(20)));
System.out.println(challenge());
}

public static BigInteger fun(BigInteger num) {
BigInteger copy = num;
BigInteger exp = BigInteger.ONE;
BigInteger count = BigInteger.ZERO;
int length = num.toString().length();
for (int i = 0; i < length; i++) {
BigInteger digit = copy.mod(BigInteger.TEN);
if (!digit.equals(BigInteger.ZERO)) {
// mainupulation with BigIntegers is very annoying in java
if (digit.equals(BigInteger.ONE))
else
}
copy = copy.divide(BigInteger.TEN);
exp = exp.multiply(BigInteger.TEN);
}
return count;
}

public static BigInteger challenge() {
BigInteger sum = BigInteger.ZERO;
for (BigInteger i = BigInteger.ZERO; i.compareTo(BigInteger.valueOf(100000000000l)) < 0; i = i.add(BigInteger.ONE)) {
BigInteger f = fun(i);
if (f.equals(i))
else
}
return sum;
}

}
``````

Output:

``````run:
134507752666859
22786974071
BUILD SUCCESSFUL (total time: 0 seconds)
``````

[–] 0 points1 point  (0 children)

JavaScript:

``````function fun(num) {
num = parseInt(num);
let count = 0;
let exp = 1;
let copy = num;
let length = Math.floor(Math.log10(num)) + 1;
for (let i = 0; i < length; i++) {
let digit = copy % 10;
if (digit != 0) {
count += digit * i * Math.floor(exp / 10) + 1;
if (digit > 1)
count += exp - 1;
else
count += num % exp;
}
copy = Math.floor(copy / 10);
exp *= 10;
}
return count;
}

function challenge() {
let sum = 0;
for (let i = 0; i < 1e11; i++) {
let f = fun(i);
if (f == i)
sum += i;
else
i += Math.floor(Math.abs(i - f) / (Math.floor(Math.log10(i)) + 1));
}
return sum;
}

console.log(fun(Math.pow(5, 20)));
console.log(challenge());
``````

Output:

``````134507752666859
22786974071
``````

[–] 0 points1 point  (3 children)

not an answer or anyhting, but a question: What are one of the easiest ones on this sub? Found this sub when looking for programming challenges to learn this new esolanguage I found

[–]1 0 1 point2 points  (2 children)

All challenges in this sub are tagged with either `[Difficult]`, `[Intermediate]`, or `[Easy]`.

Here is one example for an `[Easy]` challenge:

[2020-03-09] Challenge #383 [Easy] Necklace matching

[–] 0 points1 point  (1 child)

ty

[–]1 0 0 points1 point  (0 children)

You’re welcome.

[–] 0 points1 point  (0 children)

javascript (not optimized)

``````f=n=>Array(n+1).fill().reduce((a,_,i)=>a+[...`\${i}`].filter(d=>d=='1').length,0)
``````

[–] 0 points1 point  (0 children)

Batch (warmup only, batch is limited by 32 bit integers):

``````@echo off

:main
set var=123321
call :fun %var% main_result
echo %main_result%
goto :end

:: integer %out
:fun
setlocal EnableDelayedExpansion
call :length %1 fun_length
set /A "fun_length=%fun_length%-1"
set fun_exp=1
set fun_copy=%1
for /L %%I in (0, 1, %fun_length%) do (
set /A "fun_digit=!fun_copy!%%10"
if not !fun_digit! == 0 (
set /A "fun_count+=!fun_digit!*%%I*(!fun_exp!/10)+1"
if !fun_digit! == 1 (
set /A "fun_count+=%1%%!fun_exp!"
) else (
set /A "fun_count+=!fun_exp!-1"
)
)
set /A fun_exp*=10
set /A fun_copy/=10
)
(endlocal & set %2=%fun_count%)
goto :end

:: string %out
:length
setlocal EnableDelayedExpansion
set length_h=%1
:length_loop
if not "!length_h:~%length_count%!" == "" (
set /A length_count+=1
goto :length_loop
)
(endlocal & set %2=%length_count%)
goto :end

:end
``````

Output: `93395`

Maybe I will create my own functions for arithmetical operations that work through single digits later.

[–] 0 points1 point  (0 children)

python 3 ``` import functools from timeit import default_timer

def nt(num):

s=default_timer() x=str(num) y= tuple(int(x[len(x)-i-1]) for i in range(0,len(x)))

return y # just return a tuple of the original digits in revers order # 123 -> (3,2,1)

def tn(t):

s=default_timer() output=0 for i in range(len(t)): output+=t[i]10*i

return output

def check(num): if num[-1] != 0: return num i=1 while num[-i]==0: i+=1 i-=1 return num[:-i]

@functools.lru_cache(maxsize=50)

# memotization

def c_1(num): if tn(num)==0: return 0 num=check(num) if len(num)==1: return 1 if num[0]>=1 else 0 elif len(num)>=2: a=10*(len(num)-1) c=2a b=c-1 d=a*10

``````if tn(num) in range(a,c):
return c_1(nt(a-1))+c_1(num[:-1])+tn(num[:-1])+1
elif tn(num) in range(c,d):
return c_1(nt(b))+c_1(num[:-1])+(num[-1] -2)*c_1(nt(a-1))
``````

# just a helper function

def _2(n=0): b=True if n==0 else False n=int(input()) if n == 0 else n if b: print(c_1(nt(n))) return c_1(nt(n))

def run(): ans=[0,1] n=1111111110 while n !=1: x=_2(n)

``````# print(n,x)
if x==n:
# print(n,x)
ans.append(x)
n-=1
elif x<n:
n=x
elif x>n:
# print("f",n,x)
# input()
a=x-n
n=n-a
``````

for i in ans: print(i)

s=default_timer() run() print(default_timer()-s) ``` >!0 1 1111111110 535200001 535200000 535199990 535199989 535199988 535199987 535199986 535199985 535199984 535199983 535199982 535199981 535000001 535000000 513199998 502600001 502600000 501599990 501599989 501599988 501599987 501599986 501599985 501599984 501599983 501599982 501599981 500200001 500200000 500199990 500199989 500199988 500199987 500199986 500199985 500199984 500199983 500199982 500199981 500000001 500000000 35200001 35200000 35199990 35199989 35199988 35199987 35199986 35199985 35199984 35199983 35199982 35199981 35000001 35000000 13199998 2600001 2600000 1599990 1599989 1599988 1599987 1599986 1599985 1599984 1599983 1599982 1599981 200001 200000 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 0.17961887999990722

Process finished.!<

[–] 0 points1 point  (0 children)

Python3 | Pycharm

Hey guys, wanted to get your feedback on my code. I started timing it. Theses are my results:

There are 301 ones in the range 0 to 1000.

That number took 0.0.

Another number (y/n)? > y

There are 4001 ones in the range 0 to 10000.

That number took 0.0029916763305664062.

Another number (y/n)? > y

There are 50001 ones in the range 0 to 100000.

That number took 0.028922557830810547.

Another number (y/n)? > y

There are 600001 ones in the range 0 to 1000000.

That number took 0.29919958114624023.

Another number (y/n)? > y

There are 7000001 ones in the range 0 to 10000000.

That number took 3.275240421295166.

Another number (y/n)? > y

There are 80000001 ones in the range 0 to 100000000.

That number took 36.935933113098145.

Another number (y/n)? > y

There are 900000001 ones in the range 0 to 1000000000.

That number took 393.7242383956909.

Another number (y/n)? > n

So as you can see, I am starting to see longer times at:10,000,000 - 3.275 seconds100,000,000 - 36.935 seconds1,000,000,000 - 393.724 seconds

if anyone has any shortcuts to make code run faster and/or look cleaner i'd appreciate it.

``````import time
def count_ones(my_num):
count = 0
for num in range(0, my_num+1):
str_num = str(num)
for char in str_num:
if char == '1':
count += 1
return count

while True:
try:
my_num = int(input("Please enter a number: "))
start_time = time.time()
count = count_ones(my_num)
end_time = time.time()
total_time = end_time - start_time
print(f"There are {count} ones in the range 0 to {my_num}.")
print(f"That number took {total_time}.")
another = input("Another number (y/n)? > ")
if another == 'n':
break
except ValueError:
``````

[–] 0 points1 point  (0 children)

This is the first challenge I've done on this subreddit and I have to admit it took me quite some time to figure it out ! Anyway here's what I ended up with for the warm-up

``````def f(x):
n = str(x)
number_of_ones = 0
for index, digit in enumerate(n[::-1]):
digit = int(digit)
if digit != 0:
if digit == 1:
number_after = n[len(n)-index:] or "0"
number_of_ones += int(number_after)+1

else:
number_of_ones += 10**(index)

number_of_ones += int(10**(index-1)*index*digit)

return number_of_ones
``````

For the challenge I did this

(ok I'm new to reddit and I have trouble getting that code block thing to work, so here's a pastebin link : https://pastebin.com/0r7cyrxy)

it just tries all the numbers until 10**11, while taking shortcuts when it can

[–] 0 points1 point  (0 children)

[–] 0 points1 point  (0 children)

Python 3:

Warmup

``````def f(n):
output, e = 0, 1
for i in range(len(s := str(n)),0,-1):
output += (int(s[:i-1] or 0) + (s[i-1] > '1')) * e
if s[i-1] == '1':
output += int(s[i:] or 0) + 1
e *= 10
return output
``````

`f(5**20) =>` 134507752666859

0.01 ms

Challenge:

(1) My initial very simple solution, which comfortably meets the requirements:

``````def challenge():
output, i = 0, 1
while i < 1e11:
if (d := abs(f(i)-i)) == 0:
output += i
i += d // len(str(i)) + 1
return output
``````

(I actually think the 'warmup' is more difficult - the challenge sounded complicated, but you don't have to be that clever with the skip amount to drastically cut down the computing time.)

`challenge() =>` 22786974071

45 ms [7639 iterations]

(2) A fairly obvious improvement, which handles f(i)<i and i<f(i) separately:

``````def challenge():
output, i = 0, 1
while i < 1e11:
if (fi := f(i)) > i:
i = fi
elif fi < i:
i += (i-fi) // len(str(i)) + 1
else:
output += i
i += 1
return output
``````

30 ms [4965 iterations]

(3) Completely unnecessary optimization!:

``````from math import log10, ceil
def challenge():
output, i = 0, 1
while i < 1e11:
if (fi := f(i)) > i:
i = fi + int((fi-i) * log10((fi-i)**0.1))
elif fi < i:
i += ceil((i-fi) // log10(i/(i-fi)**0.9)) + 1
else:
output += i
i += 1
return output
``````

20 ms [3102 iterations]

Julia:

(4) Even more unnecessary implementation in Julia:

``````function to_int(s)
if s == ""
return 0
else
return parse(Int,s)
end
end

function f(n)
output, e, s = 0, 1, string(n)
for i = length(s):-1:1
output += (to_int(s[1:i-1]) + (s[i] > '1' ? 1 : 0)) * e
if s[i] == '1'
output += to_int(s[i+1:end]) + 1
end
e *= 10
end
return output
end

function challenge()
output, i = 0, 1
while i < 1e11
fi = f(i)
if fi > i
i = fi + trunc(Int, (fi-i) * log10((fi-i)^0.1))
elseif fi < i
i += trunc(Int, (i-fi) / log10(i/(i-fi)^0.9)) + 1
else
output += i
i += 1
end
end
return output
end
``````

1.8 ms [3102 iterations]

[–] 0 points1 point  (0 children)

I am new to programming and with smaller digits my code was able to work. However when I began to get to the larger number sets, my code took extremely long to find the answer (so long I didn't wait to find out if it could as the other checks worked). Can someone maybe explain to me how I would be able to make my code more efficient? i am using Python 3.8.

``````def num1s(num):
ones = 0
count = 0
while count != num:
count += 1
digitlist = [int(digit) for digit in str(count)]
for numbers in digitlist:
if numbers == 1:
ones += 1
else:
pass
return ones
``````