47
\$\begingroup\$

Task

Given \$n\$, output position of the last odd digit in the decimal representation of \$2^n\$ (counting from the end).

Rules

  • There are no odd digits for \$n=1,2,3,6,11\$ \$(2, 4, 8, 64, 2048)\$ - you may output anything that is not a positive integer for them (no need to be consistent).
  • You choose whether to handle \$n=0\$.
  • Standard I/O rules.
  • This is .

Test-cases

    n answer   (2^n)
    1     NA       2
    2     NA       4
    3     NA       8
    4      2      16
    5      2      32
    6     NA      64
    7      3     128
    8      2     256
    9      2     512
   10      4    1024
   11     NA    2048
   12      2    4096
   13      2    8192
   14      3   16384
   15      3   32768
   16      2   65536
   17      2  131072
   18      3  262144
   19      6  524288
   20      2 1048576

Inspired by this Mathematics SE post and comments on OEIS A068994.

\$\endgroup\$
11
  • 7
    \$\begingroup\$ 14 answers and 7 votes... Imho you don’t have to vote for everything, but if you answer... \$\endgroup\$
    – lesobrod
    Jun 16, 2023 at 14:02
  • 2
    \$\begingroup\$ @lesobrod - I have no hard feelings towards the community here. Simple challenges like this one very often attract many answers and don't tend to gather many upvotes. \$\endgroup\$
    – pajonk
    Jun 16, 2023 at 14:21
  • 11
    \$\begingroup\$ @lesobrod That's one of my pet peeves here. How can a challenge be worth answering but not worth upvoting? \$\endgroup\$
    – Luis Mendo
    Jun 16, 2023 at 14:39
  • 3
    \$\begingroup\$ Could we get clarity on what "you may output anything that is not a positive integer for them" means? May we error rather than output? May we never halt? \$\endgroup\$ Jun 16, 2023 at 16:35
  • 3
    \$\begingroup\$ @JonathanAllan I'll allow erroring, but I'd like solutions to terminate (best reference I could find on Meta). Counting may start from 0 - for me that's covered in standard sequence I/O rules. \$\endgroup\$
    – pajonk
    Jun 16, 2023 at 18:08

39 Answers 39

1
2
2
\$\begingroup\$

J, 26 bytes

2{.^:$@I.@:|2x,.@|.&.":@^]

0-indexed. Returns an empty array for no odd digit.

Attempt This Online!

2{.^:$@I.@:|2x,.@|.&.":@^]
            2x          ^]  NB. 2^input using extended precision literal
                       @    NB. then
              ,.@|.&.":     NB. stringify→reverse then columnize→convert to int
2          |                NB. mod 2 the resulting digit list
         @:                 NB. then
       I.                   NB. find truthy indices
      @                     NB. then
 {.^:$                      NB. get first item, {., if, ^:, the rank, $, is not 0.
\$\endgroup\$
2
\$\begingroup\$

BQN, 22 bytes

1⊸+|1+·⊐⟜1∘⌊2|2⊸⋆÷10⋆↕

Try it at BQN REPL

First find the 0-based index of the first odd digit of the power-of-2 of input 𝕩 (or return 𝕩 if all digits are even):

⊐⟜1∘⌊2|2⊸⋆÷10⋆↕
        2⊸⋆       # 2 to the power of input
           ÷      # divided by
            10    # 10
              ⋆   # to the power of 
               ↕  # range from 0..input;
       |          # modulo
      2           # 2;
     ⌊            # floor;
    ∘             # applied to
⊐⟜1               # find first instance of 1

Then fix the cases with all-even digits: change to 1-based indices and output this modulo 𝕩+1 (so all-even-digit inputs become zero):

1⊸+|1+·
      ·           # last result 
    1+            # add 1;
   |              # modulo;
1⊸+               # input plus 1
\$\endgroup\$
2
\$\begingroup\$

Racket – 182 bytes

(define(f n)(let l([L(reverse(map(λ(c)(-(char->integer c)48))(string->list(number->string(expt 2 n)))))][I 0])(cond[(odd?(list-ref L I))I][(>(-(length L)1)I)(l L(+ I 1))][#t 'na])))

Try it online!


Explanation

We first obtain the list of digits in reversed order of the number \$ 2^n \$ and start the index at 0 since Racket uses 0-based indexing. When we convert the number from a string to a list, the digits are represented in ASCII characters. So to extract the digits numeric value we need to subtract 48 from the character's ASCII value (48 in ASCII is the character 0).

(define (last-odd n)
  (let loop ([lst (reverse (map (lambda (char) (- (char->integer char) 48))
                                (string->list (number->string (expt 2 n)))))]
             [index 0])
    ...))

Once we have the list of reversed digits, we can begin looping. We create a conditional statement that checks if the current digit is odd. If it is, we return the index. If it isn't odd, we move on to the next check which checks whether we can still loop through the list. If we can, great, we then loop. If all fails, we return 'na.

(define (last-odd n)
  (let loop ([lst (reverse (map (lambda (char) (- (char->integer char) 48))
                                (string->list (number->string (expt 2 n)))))]
             [index 0])
    (cond [(odd? (list-ref lst index)) index]
          [(> (sub1 (length lst)) index) (loop lst (add1 index))]
          [#t 'na])))

Conclusion

I'd like to end this off with an interesting experiment. I'd like to see how this function looks like on a plot. To do this, we can import Racket's plot library:

(require plot)

Now to customize our plot, we can use parameterize to set configurations.

(require plot)

(parameterize ([plot-width 600]
               [plot-height 480]
               [plot-title "Plot that shows the positions of the last odd digit in 2^n (0 been the last digit)."]
               [plot-x-label "n"]
               [plot-y-label "Last odd digit."]
               [plot-new-window? #t])
  ...)

This will open a new window, set its title, set the label of the x and y axes and set the width and height of the plot. Cool! Now how do we draw on the plot? Simple!

Racket's plot package has a function called plot that plots what ever renderer is in its argument. Since we are using a line graph, we use a line renderer called lines.

  (plot (lines ...))

This renderer receives a sequence of vector points in the form of #(x y). We can programmatically define this sequence using a for/fold loop.

  (plot (lines (for/fold ([lst empty]) ([index (in-range 0 200)])
                 (let ([result (f index)])
                   (cons (vector index (if (equal? 'na result) 0 result))
                         lst)))))

The first argument of the loop is an empty list called lst that will be filled after each iteration. The index argument is an iterator that is constructed before the iteration begins. If index reaches 199, the loop stops and lst is returned.

cons prepends a value to an existing list. In our case we create a new vector in the form of #(x y) where x is the current index value and y is the result of (f index). We then prepend this new vector to lst and replace the old lst with the new list by returning the constructed list.

Putting this all together:

#lang racket

; -- Paste in the golfed code -- ;

(require plot)

(parameterize ([plot-width 600]
               [plot-height 480]
               [plot-title "Plot that shows the positions of the last odd digit in 2^n (0 been the last digit)."]
               [plot-x-label "n"]
               [plot-y-label "Last odd digit."]
               [plot-new-window? #t])
  (plot (lines (for/fold ([lst empty]) ([index (in-range 0 200)])
                 (let ([result (f index)])
                   (cons (vector index (if (equal? 'na result) 0 result))
                         lst))))))

Which renders the following:

Plot of f(x) where 0 <= x < 200

Pretty interesting! Have an amazing weekend!

\$\endgroup\$
2
\$\begingroup\$

x86, 20 bytes

Assumes input is in ecx and that edx is cleared.

B3 0A B0 01 D3 E0 B1 01 F7 FB 89 C2 FF C1 83 E2 01 74 F5 C3
        mov $10, %bl;     # b = divisor
        mov $1, %al;      # a = 1
        shll %cl, %eax;   # a = 1<<n = 2**n
        mov $1, %cl;      # c = 1, first digit is always even

    loop:
        idiv %ebx;        # a / 10
        movl %eax, %edx;  # a->d for comparison / clearing
        incl %ecx;        # c += 1
        andl $1, %edx;    # a % 2, clears edx if 0, otherwise loop is over
        jz loop;          # if a%2 == 0, loop again

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Swift 5.9, 70 68 bytes

var o={(n:Int)in String(2<<n).reversed().index{Int("\($0)")!%2==1}!}

0-indexed, throws a force-unwrap error when there aren't any odd characters.

Throws a deprecation warning when compiling on modern Swift versions; ignore it.

\$\endgroup\$
2
\$\begingroup\$

Uiua, 15 bytes

⬚∞⊢⊚⇌◿2-@0°⋕ⁿ:2

Try it!

0-indexed; returns for no answer.

⬚∞⊢⊚⇌◿2-@0°⋕ⁿ:2
            ⁿ:2  # 2 to the input power
          °⋕     # unparse
       -@0       # convert to digits
     ◿2          # modulo 2
    ⇌            # reverse
   ⊚             # indices of 1s
⬚∞⊢              # first one, or infinity if none exist
\$\endgroup\$
1
\$\begingroup\$

Python 2, 64 bytes

x=0
for y in`2**input()`[::-1]:
 x+=1
 if int(y)%2:print x;break

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Raku, 31 bytes

{(2**$_ .flip~~/<[13579]>/).to}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pip, 8 bytes

R%*Ea@?1

Outputs 0-indexed: e.g., the output for 2^12 (4096) is 1. Outputs nothing if there is no odd digit.

Attempt This Online!

Explanation

R%*Ea@?1
    a    ; Command-line argument
   E     ; 2 to that power
 %*      ; Take each digit mod 2
R        ; Reverse
     @?1 ; Find index of first occurrence of 1
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.