Partial sums of the Kempner series

Question

The Kempner series is a series that sums the inverse of all positive integers that don't contain a "9" in their base-10 representations (i.e., \$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + .. + \frac{1}{8} + \frac{1}{10} + ...\$).

It can be shown that, unlike the Harmonic series, the Kempner series converges (to a value of about 22.92067661926415034816).

Your task is to find the partial sums of the Kempner series. These are the ways you can do it:

• Take a number \$n\$, and return the sum of the inverse of the first \$n\$ numbers that don't have a "9" in them, which is the \$n\$th partial sum of the series.
• Take a number \$n\$, and return the first \$n\$ partial sums of the series.
• Don't take any input and output the partial sums infinitely.

You can choose if your input is 0-indexed or 1-indexed.

Your algorithm result's distance from the correct value may not be over \$10^{-4}\$, for all possible values of \$n\$. While your algorithm should work theoretically for all values for N, you may ignore inaccuracies coming from floating-point errors.

Test cases, in case of returning the \$n\$th partial sum, 0-indexed:

0 -> 1.0
1 -> 1.5
9 -> 2.908766...
999 -> 6.8253...

Standard loopholes are disallowed.

This is code-golf, so the shortest answer in bytes wins.

Answer 1

Jelly, 7 6 bytes

Rb9ḌİS

Try it online!

-1 byte thanks to @Razetime

Takes input 1-indexed as an argument (footer on TIO converts to 0-indexed like in test cases)

Returns the nth partial sum

How it Works

Let's look at the denominators in base 10:

\$[1, 2, 3, 4, 5, 6, 7, 8, 10,11,12,13,...]\$ (base 10)

Since these consist of the nine base-9 digits, we can interpret them as base 9 strings:

\$[1_9, 2_9, 3_9, 4_9, 5_9, 6_9, 7_9, 8_9, 10_9, 11_9, 12_9, 13_9, ...]\$

\$=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]\$ (base 10)

So all of the denominators can be generated as natural numbers, converted to base 9, then interpreted as base 10.

Rb9ḌİS - main link, taking n (1-indexed)
R       - convert to list [1..n]
 b9     - convert each natural number to base 9
   Ḍ   - interpret each base-9 string as base 10 (decimal)
    İ  - reciprocal
     S - sum

Answer 2

Ruby, ^{52 39} 36 bytes

-13 bytes thanks to Dingus!

-3 bytes thanks to Sisyphus

x=0;"#$."[?9]||p(x+=1r/$.)while$.+=1

Try it online!

Prints all values.

Answer 3

05AB1E, 9 5 bytes

-4(!) bytes thanks to Command Master!

Outputs one value 1-indexed

L9BzO

Try it online! or Try all cases!

L      # push the range [1..n]
 9B    # convert each number to base 9
       # this yields the first n natural numbers that don't contain a 9
   z   # take reciprocal of each number
    O  # sum the list

Answer 4

Scala, 56 bytes

Stream from 1 filterNot(_+""toSet 57)take _ map 1.0./sum

Try it online!

1-indexed. Returns the sum of the inverses of the first \$n\$ numbers.

Stream from 1      //Infinite list of integers, starting at 1
  filterNot(       //Remove the ones with a 9
    _ + ""         //Convert to string
      toSet        //A Set is also a predicate. Check if it contains
      57)          //57, '9' as an integer
  take _           //Take the first n numbers
  map 1.0./        //Divide 1 by each
  sum              //Sum them

Just for completeness, 58 bytes

(Stream.from(1)filterNot(_+""toSet 57)scanLeft.0)(_+1.0/_)

Try it online!

This is an infinite stream of partial sums, but also a function that gives the \$n\$th partial sum (1-indexed). You can also use take on it to get the first \$n\$ partial sums. Unfortunately, it's a little longer than the version above.

Answer 5

Jelly, 8 bytes

1w9¬$#İS

Try it online!

1-indexed, takes input from STDIN, returns the \$n\$th partial sum

My last Jelly answer of the year, and it just so happens to outgolf Husk!

How it works

1w9¬$#İS - Main link. Takes no arguments
1   $#   - Find the first n numbers that meet the following criterion:
 w9      -   The index of 9 in the number’s digits...
   ¬     -   ...is 0 (i.e. 9 is not in the digits)
      İ  - Invert each number
       S - Sum

Answer 6

Husk, 12 10 bytes

Saved 2 bytes on both solutions thanks to @Razetime!

ṁ\↑fȯ¬#9dN

Try it online!

It's been a while since my last Husk answer. This one outputs the \$n\$th number. It outputs a fraction, but I've checked and it seems to be correct.

Explanation

ṁ\↑fȯ¬#9dN
         N    Infinite list of natural numbers
   f          Filter by predicate:
        d     Digits in base 10
      #9      Number of occurrences of digit 9
     ¬        Negate that
  ↑           Take the first n elements (implicit input)
ṁ\            Map each to its reciprocal
ṁ             And sum

Infinite sequence, also 12 10 bytes

∫m\fȯ¬#9dN

Try it online!

Answer 7

J, 20 bytes

1#.10%@#.9#.inv>:@i.

Try it online!

I just wanted to see if I could golf fireflame's excellent Jelly answer in J.

1 based indexing.

• >:@i. Integers 1..argument
• 9#.inv Each as a list of digits in base 9
• 10#. Back to single number in base 10
• %@ Reciprocal of each
• 1#. Sum

Answer 8

Husk, ⁸ 7 bytes

ṁȯ\dB9ḣ

Try it online!

Outputs the \$n^{th}\$ partial sum. I tried using İ\ from here, but it's longer.

Uses fireflame's idea.

-1 byte from user.

Explanation

∫mȯ\dB9N
       N the list of natural numbers
 mȯ      map to:
     B9  base 9 digits
    d    represented as base 10 number
   \     take reciprocal
∫        take the cumulative sum

Answer 9

Python 2, 54 bytes

f=lambda k,n=1,b=0:k<2or b/n+f(k-b,n+1,1.-('9'in`~n`))

Try it online!

One-indexed. Avoids repeating the '9'in`n+1` by passing it as an optional argument b to the next iteration of the function where the actual calculation is done.

58 bytes

f=lambda k,n=1.:k and f(k-1+('9'in`n`),n+1)-~-('9'in`n`)/n

Try it online!

59 bytes

f=lambda k,n=1:'9'in`n`and f(k,n+1)or k and 1./n+f(k-1,n+1)

Try it online!

62 bytes

lambda k:sum([1./n for n in range(1,k*k+1)if~-('9'in`n`)][:k])

Try it online!

The k*k+1 can be 2**k, saving a byte but making the code really slow.

64 bytes

s=0
n=1
exec"while'9'in`n`:n+=1\ns+=1./n;n+=1\n"*input()
print s

Try it online!

---

Python 3.8 (pre-release), 53 bytes

f=lambda k,n=1:k and(b:=max(str(n))<'9')/n+f(k-b,n+1)

Try it online!

Saved one byte thanks to @dingledooper.

Answer 10

Charcoal, 11 bytes

ＩΣ∕¹ＩＥＮ⍘⊕ι⁹

Try it online! Link is to verbose version of code. 1-indexed. Explanation:

     Ｎ      Input number
    Ｅ       Map over implicit range
         ι  Current index
        ⊕   Incremented
       ⍘  ⁹ Convert to base 9 as a string
    Ｉ       Vectorised cast to integer
  ∕¹        Vectorised reciprocal
 Σ          Sum
Ｉ           Cast to string
            Implicitly print

Answer 11

Python 2, 78 77 bytes

def f(n,i=.0,s=0):
 while n:
	i+=1
	while"9"in`i`:i+=1
	s+=1/i;n-=1
 return s

Try it online!

Answer 12

JavaScript (Node.js), 30 bytes

f=n=>n&&1/n.toString(9)+f(n-1)

Try it online!

Convert \$n\$ to base 9, and read the converted result as base 10. Then inverse it. You will get the \$n\$th item.

Answer 13

Japt -mx, 6 bytes

1-indexed

1/°Us9

Try it

Answer 14

Haskell, 45 44 42 bytes

f=scanl(+)0[1/x|x<-[1..],all(<'9')$show x]

Try it online!

Infinite list. 44 byte thanks to ovs, who suggested all(<'9') to replace not$elem '9'. 42 bytes thanks to Donat, who suggested 1 to replace 1.0.

Answer 15

Perl 5, 26 bytes

/9/||say$a+=1/$_ while++$_

Try it online!

Answer 16

AWK, 37 bytes

{for(;++i<=$1;)i~9?$1++:n+=1/i;$1=n}1

Try it online!

{
for(;++i<=$1;)  #loops while i<= the input.
                # also increments the variable 1 every loop.

  i~9?    # if there is a 9 in _i_
  $1++:   # skips this _i_, adding 1 to $1
  n+=1/i; # otherwise, adds 1/i to _n_

$1=n  # in the end, assigns _n_ to $1
}
1  # prints $1
```

Answer 17

Wolfram Language (Mathematica), 42 bytes

Tr[1/FromDigits/@Range@#~IntegerDigits~9]&

Try it online!

Answer 18

JavaScript (ES6), 46 bytes

1-indexed.

f=(n,i=1)=>n&&(/9/.test(i)?0:n/n--/i)+f(n,i+1)

Try it online!

Answer 19

R, 94 93 92 64 59 bytes

Thanks to Dominic van Essen for suggesting a grepl shortcut!

n=scan()+2;while(n<-n-1){F=F+1/T;while(grepl(9,T<-T+1))0};F

Try it online!

Answer 20

R, 45 43 bytes

Edit: -2 bytes thanks to Giuseppe

x=scan();y=1:x^2;sum(1/y[!grepl(9,y)][1:x])

Try it online!

Answer 21

MathGolf, 10 bytes

∞╒gÉ9╧┌<∩Σ

Outputs the \$n^{th}\$ value with 1-based input \$n\$.

Try it online.

Explanation:

∞          # Double the (implicit) input-integer
 ╒         # Pop and push a list in the range [1,2*input]
  g        # Filter this list by,
   É       # using the following 3 characters as inner codeblock:
    9╧     #  Check that the integer contains a digit 9
      ┌    #  And invert the boolean
       <   # Only keep the first (implicit) input amount of values of the filtered list
        ∩  # Map all values to 1/n
         Σ # And sum those together
           # (after which the entire stack joined together is output implicitly as result)

MathGolf unfortunately doesn't contain base-conversion builtins, except for binary and hexadecimal. So I use a manual filter instead. The double at the start is to ensure we have enough values left after the filter for which we can keep the first input amount of values. After which we'll map them to \$\frac{1}{n}\$, and sum them together.

Answer 22

K (ngn/k), 13 bytes

+/1%10/9\1+!:

Try it online!

A similar approach to many other answers, modeled after @fireflame241's Jelly answer. Uses 1-based indices.

• 1+!: generate 1..n
• 10/9\ convert to base-9, then back to base-10
• +/1% take the sum of the inverses

Answer 23

Raku, 25 bytes

[\+] 1 X/grep {!/9/},1..*

Try it online!

This is an expression for an infinite sequence of the partial sums.

• grep { !/9/ }, 1..* is the infinite sequence of all natural numbers with no 9 digit in its decimal representation.
• 1 X/ produces the reciprocals of that sequence. (X is the cross-product metaoperator, combined here with the / division operator.)
• [\+] produces the partial sums of that sequence.

Answer 24

SmileBASIC 4, 139 bytes

Zero-indexed. Returns the nth partial sum of the series.

1  DEF F(X)REPEAT INC U,X MOD 9*POW(10,I)X=X DIV 9INC I UNTIL!X RETURN U END
2  DIM O[1]@0 UNSHIFT O,O[0]+1INC S,1/F(O[0])IF N+2>LEN(0)GOTO@0
3  ?S

---

Newline chars on lines 1 & 2 are included in byte count. The program iterates through integers 0-N, converts each value to base 9, and adds the base-10 interpreted inverse of the value to a sum. Finally, it prints the sum.

Answer 25

Perl 5, 39 bytes

sub f{my$r;$r+=!/9//$_ for 1..$_[0];$r}

Try it online!

Answer 26

C (gcc), 87 84 bytes

Saved 3 bytes thanks to ceilingcat!!!

m;float i,s;float f(n){for(i=s=0;m=n--;s+=1/i)for(;m;)for(m=++i;~m%10*m;m/=10);i=s;}

Try it online!

Inputs a \$1\$-indexed \$n\$ and returns the \$n^{\text{th}}\$ partial sum of the series.

Answer 27

x86 Machine Code (x87 FPU), 35 bytes

D9 EE 31 F6 8D 7E 0A 46 89 F0 99 F7 F7 83 FA 09 74 F5
85 C0 75 F4 89 33 DB 03 D9 E8 DE F1 DE C1 E2 E5 C3 

The above bytes define a function that computes the n^th partial sum of the Kempner series. The function defines a custom calling convention, whereby it accepts two arguments:

• The value n is passed in the ecx register (this is an unsigned 32-bit integer value).
• The address of a "scratch" memory buffer is passed in the ebx register (the buffer's size must be at least 4 bytes in length).

The function returns a single result, the n^th partial sum, at the top of the x87 FPU stack (st(0)).

Try it online!

In ungolfed assembly language mnemonics:

         ; Computes the nth partial sum of the Kempner series.
         ; Input(s):
         ;   ecx = n
         ;   ebx = address of DWORD scratch buffer
         ; Output(s):
         ;   st(0) = nth partial sum
         ; Clobber(s):
         ;   eax, [ebx], ecx, edx, esi, edi, st, flags
         Kempner:
D9 EE      fldz                         ; start with partial sum == 0.0 (at top of x87)
31 F6      xor    esi, esi              ; esi = 0
8D 7E 0A   lea    edi, [esi + 10]       ; edi = 10

         PartialSum:
46         inc    esi                   ; esi += 1
89 F0      mov    eax, esi              ; eax = esi
         
         CheckDigit:
99         cdq                          ; zero edx (normally, prefer xor edx, edx)
F7 F7      div    edi                   ; edx:eax / edi
83 FA 09   cmp    edx, 9                ; remainder == 9?
74 F5      je     PartialSum            ; skip if digit was a 9
85 C0      test   eax, eax              ; quotient  == 0?
75 F4      jnz    CheckDigit            ; loop if more digits to check
           
89 33      mov    DWORD PTR [ebx], esi  ; store esi into scratch memory buffer
DB 03      fild   DWORD PTR [ebx]       ; push value from scratch memory buffer to top of x87
D9 E8      fld1                         ; push 1.0 to top of x87
DE F1      fdivrp st(1), st(0)          ; calculate 1.0 / esi
DE C1      faddp  st(1), st(0)          ; accumulate partial sum (result is at top of x87)
E2 E3      loop   PartialSum            ; decrement ecx (n), and continue looping if non-zero
C3         ret

---

[BONUS:] x86 Machine Code (AVX), 44 bytes

31 F6 46 0F 57 C0 8D 7E 09 F3 0F 2A D6 4E 46 89 F0 99 F7 F7 83 FA
09 74 F5 85 C0 75 F4 C5 F2 2A CE C5 EA 5E C9 C5 FA 58 C1 E2 E3 C3

In ungolfed assembly language mnemonics:

             ; Computes the nth partial sum of the Kempner series.
             ; Input(s):
             ;   ecx = n
             ; Output(s):
             ;   xmm0 = nth partial sum
             ; Clobber(s):
             ;   eax, ecx, edx, esi, edi, xmm0, xmm1, xmm2, flags
             Kempner:
31 F6          xor       esi,  esi             ; \ set ESI to 1
46             inc       esi                   ; /
0F 57 C0       xorps     xmm0, xmm0            ; zero XMM0
8D 7E 09       lea       edi,  [esi + 9]       ; set EDI to 10
F3 0F 2A D6    cvtsi2ss  xmm2,  esi            ; set XMM2 to 1 (from ESI)
4E             dec       esi                   ; set ESI back to 0

             PartialSum:                         
46             inc       esi
89 F0          mov       eax,  esi

             CheckDigit:                         
99             cdq       
F7 F7          div       edi
83 FA 09       cmp       edx,  9
74 F5          je        PartialSum
85 C0          test      eax,  eax
75 F4          jne       CheckDigit

C5 F2 2A CE    vcvtsi2ss xmm1, xmm1, esi
C5 EA 5E C9    vdivss    xmm1, xmm2, xmm1
C5 FA 58 C1    vaddss    xmm0, xmm0, xmm1
E2 E3          loop      PartialSum
C3             ret

This is larger, since the AVX instructions require more bytes to encode than the x87 instructions. It is essentially the direct translation of the above function targeting the x87 FPU, except that I had to be a bit clever when loading "1.0" in the AVX (xmm2) register. Basically, I eagerly set esi to 1, load it into xmm2 using the convert-from-integer instruction, and then set esi back to 0. Since inc and dec are 1-byte instructions, this is the cheapest way that I could find.

Answer 28

Zsh -o forcefloat, ⁴¹ 40 bytes

for ((;++n;))((n[(I)9]))||echo $[a+=1/n]

Try it online!

Outputs infinitely.

Explanation:

for ((;++n;))((n[(I)9]))||echo $[a+=1/n]
                                           implicitly intitialise $n and $a to 0
for ((;   ;))                              loop while
       ++n                                  increment $n (always truthy)
                        ||                   if not
               n[(I)9]                        the index of "9" in $n
             ((       ))                       is not zero,
                               $[a+=   ]      then increase $a by
                                    1/n        the reciprocal of $n
                          echo                and print $a

Answer 29

Vyxal s, 39 bits¹, 4.875 bytes

9c¬)ȯĖ

Try it Online!

1-indexed.

Explained

9c¬)ȯĖ
   )ȯ  # First #input numbers which:
 c¬    #    don't contain
9      #    the number 9
     Ė # reciprocals
# summed by the s flag