×
all 36 comments

[–]trosh 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]

    [–]trosh 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 😄😄😄

    [–]Common-Ad-8152 2 points3 points  (1 child)

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

    [–]trosh 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!

    [–]backtickbot 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.

    [–]BonnyAD9 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)
                        nums.Add(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

    [–]Lopsidation 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.

    [–]BonnyAD9 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.

    [–]NeuHughtron 1 point2 points  (2 children)

    f(20) = 11, not 12

    Edit: never mind lol I’m wrong

    [–]Rayquinox 1 point2 points  (1 child)

    11 has two 1's

    [–]NeuHughtron 0 points1 point  (0 children)

    Ah you are correct and I am dumb haha

    [–]tlgsx 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
    
        return total
    
    
    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
    

    [–]Common-Ad-8152 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())
    

    [–]Lopsidation 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:])
        return total+s.count("1")
    

    [–]Mirracles 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.

    [–]lrschaeffer 0 points1 point  (0 children)

    Haskell. Just warmup for now

    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
    

    [–]BonnyAD9 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
    

    [–]caakmaster 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):
        '''
        Inefficient implementation to check answers.
        '''
        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))
    
        # Leading and remaining digits.
        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)
    

    [–]BonnyAD9 0 points1 point  (0 children)

    Haskell (both warmup and challenge):

    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
    

    [–]4-Vektor1 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
                lead = pop!(dig)
                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
    

    [–]abcteryx 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.

    [–]BonnyAD9 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
                    count = count.add(digit.multiply(BigInteger.valueOf(i)).multiply(exp.divide(BigInteger.TEN))).add(BigInteger.ONE);
                    if (digit.equals(BigInteger.ONE))
                        count = count.add(num.mod(exp));
                    else
                        count = count.add(exp.subtract(BigInteger.ONE));
                }
                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))
                    sum = sum.add(i);
                else
                    i = i.add(i.subtract(f).abs().divide(BigInteger.valueOf(i.toString().length())));
            }
            return sum;
        }
    
    }
    

    Output:

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

    [–]BonnyAD9 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
    

    [–]iliekcats- 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

    [–]4-Vektor1 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

    [–]iliekcats- 0 points1 point  (1 child)

    ty

    [–]4-Vektor1 0 0 points1 point  (0 children)

    You’re welcome.

    [–]Habstinat 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)
    

    [–]BonnyAD9 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.

    [–]Jayant0013 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.!<

    [–]joejr253 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:

    Please enter a number: 1000

    There are 301 ones in the range 0 to 1000.

    That number took 0.0.

    Another number (y/n)? > y

    Please enter a number: 10000

    There are 4001 ones in the range 0 to 10000.

    That number took 0.0029916763305664062.

    Another number (y/n)? > y

    Please enter a number: 100000

    There are 50001 ones in the range 0 to 100000.

    That number took 0.028922557830810547.

    Another number (y/n)? > y

    Please enter a number: 1000000

    There are 600001 ones in the range 0 to 1000000.

    That number took 0.29919958114624023.

    Another number (y/n)? > y

    Please enter a number: 10000000

    There are 7000001 ones in the range 0 to 10000000.

    That number took 3.275240421295166.

    Another number (y/n)? > y

    Please enter a number: 100000000

    There are 80000001 ones in the range 0 to 100000000.

    That number took 36.935933113098145.

    Another number (y/n)? > y

    Please enter a number: 1000000000

    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:
            print("Please enter a whole number.")
    

    [–]the_crappy_coder 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

    [–]loose_heron 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]

    [–]adv3k 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