title: Denominator of harmonic series

text:
# Question
Title: Denominator of harmonic series
Earlier, we did the pseudofactorial of a number, which is the LCM of the numbers from `1` to `n`.

It would be useful in adding fractions together.

However, we find that the denominator of `1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6` is `20` instead of the pseudofactorial of `6`, which is `60`.

Your task is to find the denominator of `1/1 + 1/2 + ... + 1/n` given positive integer `n`.

# Testcases

```
 n result
 1 1
 2 2
 3 6
 4 12
 5 60
 6 20
 7 140
 8 280
 9 2520
10 2520
11 27720
12 27720
13 360360
14 360360
15 360360
16 720720
17 12252240
18 4084080
19 77597520
20 15519504
21 5173168
22 5173168
23 118982864
24 356948592
25 8923714800
26 8923714800
27 80313433200
28 80313433200
29 2329089562800
30 2329089562800

```

# References

# Leaderboard

```
var QUESTION_ID=82815,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# , ~~9~~ 6 bytes

Thanks to **FryAmTheEggman** for saving 3 bytes! Code:

```
RİSg¹İ

```

**M** has a huge advantage here, because it works with fractions rather than floats. Explanation:

```
R       # Get the list [1 ... n].
 İ      # Inverse each, resulting into [1/1, 1/2, 1/3, ..., 1/n].
  S     # Sum it up. (86021/27720 for n=12)
   g¹   # Compute the greatest common denominator with n. (1/27720 for n=12)
     İ  # Calculate the inverse again. (27720 for n=12)

```

Uses the **Jelly encoding**. Try it online!.

---

Also, there is a **4-byte** solution, which outputs a leading zero sometimes (e.g. `280 -> 0280`). I'm not sure if this is allowed or not:

```
RİSV

```

Try it online!.
> 8 votes

# Answer
# Julia, 22 bytes

An anonymous function.

```
n->1.//(1:n)|>sum|>den

```
> 5 votes

# Answer
### Ruby, ~~57~~ 47 bytes

```
->n{(1..n).reduce{|a,i|a+1.to_r/i}.denominator}

```

Thanks to **Kevin Lau** for shortening this by ten bytes.
> 5 votes

# Answer
# Mathematica, 27 bytes

An anonymous function.

```
Denominator@*HarmonicNumber

```

For example:

```
 In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520

```
> 4 votes

# Answer
# Python 2, ~~69~~ 67 bytes

```
a=b=k=r=1
exec'a=a*k+b;b*=k;k+=1;'*input()
while r*a%b:r+=1
print r

```

Test it on Ideone.

### How it works

Let **H(n)** be the sum of the multiplicative inverses of the first **n** positive integers. At all times, we have that **a / b = 1 + H(k - 1)**. In fact, **a**, **b**, and **k** are all initialized to **1**, and **1 / 1 = 1 = 1 + H(0)**.

We repeat the code snippet

```
a=a*k+b;b*=k;k+=1;

```

(as a string) **n** (input) times and execute the result. In each step, we update **a**, **b**, and **k** using the identity **a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk**.

After all copies have been executed, **a / b = 1 + H(n)**, which has the same denominator as **H(n)**.

The fully reduced form of **a / b** is **(a ÷ gcd(a,b)) / (b ÷ gcd(a,b))**. Instead of calculating the greatest common divisor, we initialize **r** as **1** and keep incrementing **r** until **ra** is a multiple of **b**.

Clearly, this makes **ra** the least common multiple of **a** and **b**. Since **gcd(a,b) · lcm(a,b) = ab**, we have that **b ÷ gcd(a,b) = lcm(a,b) ÷ a = ra ÷ a = r**, making **r** the desired output.
> 4 votes

# Answer
# Haskell, 52

```
Import Data.Ratio
f n=denominator$sum[1%k|k<-[1..n]]

```

If the file is loaded into GHCI, f can be used as a function.
> 3 votes

# Answer
# MATL, ~~14~~ 13 bytes

```
:p:G:!/s1\&X<

```

**Try it online!**

### Explanation

For input *N*, the output is upper-bounded by *N*! (factorial of *N*). The code computes *n*/*k* for *n* = 1, ..., *N*! and for *k* = 1, ..., *N*. Then it sums over *k*, which gives the harmonic number multiplied by each *n*. The desired result is the index *n* of the first of those values that is an integer.
> 2 votes

# Answer
# Jelly, 9 bytes

```
!©÷RSg®®÷

```

Try it here.

```
             Argument: n
! ÷R         Compute [n!÷1, n!÷2, … n!÷n].
 ©             (And store n! in the register.)
    S        Find the sum of this list.
     g®      GCD with n!.
       ®÷    Divide n! by this GCD.

```
> 2 votes

# Answer
# 05AB1E, 8 bytes

Code:

```
!Ð¹L/O¿/

```

Explanation:

```
!         # Take the factorial of the input.
 Ð        # Triplicate this.
  ¹L      # Get the list [1 ... input].
    /O    # Divide and sum up.
      ¿   # Get the GCD of the sum and the factorial.
       /  # Divide the factorial by this.

```

There might be some accuracy problems for n \> 19 due to Python's division... Uses the **CP-1252** encoding.

Try it online!.
> 2 votes

# Answer
## Mathematica, 26 bytes

```
Denominator@Tr[1/Range@#]&

```

An unnamed function taking `n` as input and returning the denominator. Uses the standard trick of abusing `Tr` (trace) to sum the list of reciprocals.
> 2 votes

# Answer
# Husk, 6 bytes

```
is\ṁ\ḣ

```

Try it online!

Not too hard in Husk since it can do math with rational numbers. The hard part was extracting the denominator, I ended up inverting the fraction, converting it to string, and getting the first number from that string.

### Explanation

```
is\ṁ\ḣ
     ḣ     range [1..n]
   ṁ       sum the result of this function for each number:
    \        inverse
  \        invert
 s         convert to string
i          get the first number in the string (the numerator)

```
> 2 votes

# Answer
## JavaScript (ES6), 88 bytes

```
m=>{for(d=1,i=0;i<m;d*=++i);for(n=i=0;i<m;n+=d/++i);for(g=d;g;[g,n]=[n%g,g]);return d/n}

```

Only works up to m=20 because of the limits of JavaScript's numeric precision.
> 1 votes

# Answer
# Pari/GP, 30 bytes

```
n->denominator(sum(i=1,n,1/i))

```

Try it online!
> 1 votes

# Answer
# Stax, 5 bytes

```
┬ΓΣ╞]

```

Run and debug it

6 bytes without packing.
> 1 votes

# Answer
# Whispers v3, 79 bytes

```
> Input
>> 1!
>> 2∕R
>> (1]
>> Each 3 4
>> ∑5
>> 6⊓2
>> 2∕7
>> Output 8

```

Try it online!

Same idea as Lynn's Jelly answer.
> 1 votes

# Answer
# Thunno, \\$ 12 \log\_{256}(96) \approx \\$ 10 bytes

(Actually 9.88 bytes but that doesn't show up on the leaderboard)

```
Fztz!R+/SAG/

```

Attempt This Online!

Port of Adnan's 05AB1E answer.

#### Explanation

```
Fztz!R+/SAG/  # Implicit input
Fzt           # Get factorial and triplicate
   z!R+       # Push range(1, input+1)
       /S     # Divide and sum
         AG/  # Get GCD and divide

```
> 1 votes

# Answer
**Python 3, 153 150 146 142 bytes**

I'm sure this can golfed further. But I'm new here

```
f=lambda x:0**x or x*f(x-1)
z=int(input());i=f(z)
r=sum(i/y for y in range(1,z+1))
p=lambda a,b:a if b<1else not a%b+b or p(b,a%b)
print(i/p(r,i))

```
> 0 votes

# Answer
# J, 20 bytes

```
(!%!+.[:+/!%1+i.)@x:

```

Based on the approach used by @Lynn's solution.

If precision is not necessary for large values of **n** or if we can assume **n** will be passed as an extended integer, suffixed by `x`, a shorter solution can be used for **15 bytes**.

```
!%!+.[:+/!%1+i.

```

## Usage

```
   f =: (!%!+.[:+/!%1+i.)@x:
   f 30
2329089562800
   (,:f"0) >: i. 15
1 2 3  4  5  6   7   8    9   10    11    12     13     14     15
1 2 6 12 60 20 140 280 2520 2520 27720 27720 360360 360360 360360

```

## Explanation

```
(!%!+.[:+/!%1+i.)@x:  Input: n
                  x:  Convert n into an extended integer
              i.      Creates the range [0, 1, ..., n-1]
            1+        Add one to each, range is now [1, 2, ..., n]
          !           Get factorial of n
           %          Divide n! by each value in the range [1, 2, ..., n]
      [:+/            Sum those values
   !                  Get n!
    +.                Get gcd between n! and the sum
 !                    Get n!
  %                   Divide n! by the gcd and return

```
> 0 votes

# Answer
# Perl 6,  ~~36~~  32 bytes

```
~~{([+] 1.FatRat X/1..$_).denominator}~~
{([+] 1.FatRat X/1..$_).nude[1]}
```

### Explanation:

```
{
  (
    [+]        # reduce with &infix:<+>

      # the following produces a Seq of Rational numbers
      # 1/1, 1/2, 1/3 ... 1/n

      1.FatRat # FatRat.new: 1,1
      X/       # crossed using &infix:</>
      1 .. $_  # Range from 1 to the input inclusive

  ) # resulting in a FatRat

  .nude # (nu)merator (de)nominator
  .[1]  # grab the denominator
}

```

### Test:

```
my &hd = {([+] 1.FatRat X/1..$_).nude[1]}

say (1..10)».&hd; # (1 2 6 12 60 20 140 280 2520 2520)

say hd 100; # 2788815009188499086581352357412492142272
say chars hd 1000; # 433
say chars hd 10000; # 4345

```
> 0 votes

# Answer
## Hoon, 95 bytes

```
|=
@
=+
n=(gulf 1 +<)
=+
f=(roll n mul)
(div f d:(egcd f (roll (turn n |=(@ (div f +<))) add)))

```

Create list `[1...n]`, fold over it with `++mul` for the factorial, create list `[n!/1, n!/2, ... n!/n]` and sum it, find GCD of `n!` and the list, and divide the factorial by that number.

There's probably a much easier way to calculate the denominator, but I can't figure it out :/
> 0 votes

# Answer
# Axiom, 34 bytes

```
f(x)==denominator(sum(1/n,n=1..x))

```

test

```
(24) -> [[i,f(i)] for i in 1..30]
   (24)
   [[1,1], [2,2], [3,6], [4,12], [5,60], [6,20], [7,140], [8,280], [9,2520],
    [10,2520], [11,27720], [12,27720], [13,360360], [14,360360], [15,360360],
    [16,720720], [17,12252240], [18,4084080], [19,77597520], [20,15519504],
    [21,5173168], [22,5173168], [23,118982864], [24,356948592],
    [25,8923714800], [26,8923714800], [27,80313433200], [28,80313433200],
    [29,2329089562800], [30,2329089562800]]
                                       Type: List List Expression Integer

```
> 0 votes

# Answer
# PHP, 81 Bytes

```
for($p=1;$z++<$argn;$n=$n*$z+$p/$z)$p*=$z;for($t=1+$n;$p%--$t||$n%$t;);echo$p/$t;

```

Try it online!
> 0 votes

# Answer
# Japt, 12 bytes

```
l
/yNÎõ@/XÃx

```

Try it

```
l\n/yNÎõ@/XÃx     :Implicit input of integer U
l                 :Factorial
 \n               :Reassign to U
   /              :Divide by
    y             :GCD with
     N            :  Array of all inputs
      Î           :  First element (i.e., original input)
       õ          :  Range [1,NÎ]
        @         :  Map each X
         /X       :    Divide U by X
           Ã      :  End map
            x     :  Reduce by addition

```
> 0 votes

# Answer
# Factor \+ `math.unicode`, 35 bytes

```
[ 1 swap [1,b] n/v Σ denominator ]

```

Try it online!
> 0 votes

# Answer
# Arturo, 38 bytes

```
$=>[denominator∑map..1&=>reciprocal]

```

Try it
> 0 votes

---
Tags: code-golf, sequence
---


# Question
Title: Shortest code to generate a list of prime numbers within a given range
Strangely never asked before, this question pertains to the generation of a list of prime numbers within a given range using the shortest possible code. Several algorithms, such as the Sieve of Eratosthenes and trial division, are known to be effective for this purpose, but require significant code length. Is there an alternative approach or trick that can be used to generate a list of prime numbers in a more concise manner?

The focus of this question is on the optimization of code length, so answers should try to make their code as short as possible. Answers in any programming language are welcome. May the shortest code win!

### Format

You must accept two positive integers and output a list of integers in any reasonable format.

### Rules

* Your code doesn't need to handle numbers less than one.
* The range should be exclusive, i.e., `(a..b)` instead of `[a..b]` or `[a..b)`.
* Either ascending or descending ranges should be supported.
* Standard loopholes are forbidden.

### Test cases

```
11 59 -> [13,17,19,23,29,31,37,41,43,47,53]
11 3  -> [7,5]
2 2   -> []
2 3   -> []
2 4   -> [3]
4 2   -> [3]
```

# Answer
# Vyxal, 4 bytes

*+1 byte from @Jacob for informing me about the requirement for exclusive range*

```
rḢ'æ

```

Try it Online!

Finds all the primes between the first input and the second input (exclusive).

## Explanation

```
r      # Get the range from [<input 1>, ..., <input 2>-1]
 Ḣ     # Remove the first value (so it's exclusive on both ends)
  '    # of that range, filter....
   æ   # only those which are prime

```
> 4 votes

# Answer
# Factor \+ `math.primes`, 27 bytes

```
[ (a,b) [ prime? ] filter ]

```

Try it online!
> 4 votes

# Answer
# 05AB1E, 5 bytes

```
Ÿ¦¨ʒp

```

Try it online or verify all test cases.

**Explanation:**

```
Ÿ      # Convert the (implicit) input-pair to an inclusive list
 ¦¨    # Remove both the first and last item to make it an exclusive list
   ʒ   # Filter it by:
    p  #  Check whether the number is a prime
       # (after which the filtered list is output implicitly)

```
> 3 votes

# Answer
# Perl 5, 48 bytes

```
sub{grep{(1x$_)!~/^1$|^(11+)\1+$/}1+pop.."@_"-1}

```

Try it online!
> 3 votes

# Answer
# Japt, 6 bytes

```
oV Åfj

```

Try it

Essentially equivalent to 97.100.97.109's answer, though developed independently. Gets the exclusive range by getting the inclusive range between \\$\[n\_1+1,n\_2-1\]\\$. -2 bytes thanks to Shaggy

Explanation:

```
oV Åfj  full program
oV      the inclusive range between the two inputs
   Å    cut off the first and last elements
    f   filter, keeping only those that
     j    are prime

```

## Japt, 5 bytes

Inclusive range, which was banned after writing this

```
oV fj

```

```
oV  the range from input 1 to input 2
f   filter, keeping only those that
 j    are prime

```
> 2 votes

# Answer
# Arturo, 35 bytes

```
$=>[select chop drop@&..&1=>prime?]

```

Try it

```
$=>[          ; anonymous function
    select    ; take elements from
    chop      ; remove last element
    drop .. 1 ; remove first element
    @&..&     ; inclusive input range, reified
    =>prime?  ; that are prime
]             ; end function

```
> 2 votes

# Answer
# Retina 0.8.2, ~~62~~ 52 bytes

```
.+
$*
O`
M!&`(?<=(1+)¶1+)1+\1
A`^(11+)\1+$
O`
1+
$.&

```

Try it online! Takes inputs on separate lines but link is to test suite that splits on comma for convenience. Explanation:

```
.+
$*

```

Convert to unary.

```
O`

```

Sort into order.

```
M!&`(?<=(1+)¶1+)1+\1

```

Generate the exclusive range.

```
A`^(11+)\1+$

```

Remove any composite numbers.

```
O`

```

Sort into order.

```
1+
$.&

```

Convert any remaining numbers to decimal.
> 2 votes

# Answer
# Java 10, 137 bytes

```
(a,b)->{var r=new java.util.Stack();int t=0,i;for(a^=b<a?b^(t=b=a):0;++a<b;){for(i=a;a%--i>0;);if(i<2)r.add(t<1?r.size():0,a);}return r;}

```

Try it online.

**Explanation:**

```
(a,b)->{                      // Method with two integer parameters and List return-type
  var r=new java.util.Stack();//  Result-list, starting empty
  int t=0,i;                  //  Temp-integers
  for(a^=b<a?                 //  If `b` is smaller than `a`:
          b^(t=b=a):0;        //   Set `t` to `a`,
                              //   and then swap `a` and `b` by using bitwise XORs
      ++a<b;){                //  Loop in the range (a,b):
    for(i=a;                  //   Set `i` to the current `a`
        a%--i>0;);            //   Decrease `i` before every iteration with `--i`,
                              //   and continue as long as `a` is NOT divisible by `i`
    if(i<2)                   //   If `i` is 1 after the loop (which means `a` is a prime):
      r.add(t<1?              //    If `t` is 0 (which means `a` was already smaller than
                              //    or equal to `b`):
                r.size()      //     Append to the result-list
               :              //    Else (`a` was larger than `b`):
                0,            //     Prepend to the result-list instead
            a);}              //    The current prime `a`
  return r;}                  //  And finally return the result-list

```

Unlike my 05AB1E answer, the exclusive range is actually an advantage for my Java answer, since checking whether a number \\$n\geq2\\$ is a prime is 3 bytes shorter than checking whether a number \\$n\geq1\\$ is a prime (see section *Primes* in this Java tip of mine).

---

Since I was curious: using an `IntStream` is apparently **~~144~~ 143 bytes**:

```
a->b->java.util.stream.IntStream.iterate(a<b?a+1:a-1,i->b<a?i-1:i+1).limit(a<b?b+~a:a>b?a+~b:0).filter(k->{int i=k;for(;k%--i>0;);return i<2;})

```

-1 byte thanks to *@Neil*.

Try it online.

**Explanation:**

```
a->b->                        // Method with two integer parameters and IntStream return
 java.util.stream.IntStream   //  Create an IntStream
  .iterate(a<b?               //  If `a` is smaller than `b`
            a+1               //   Start at `a+1`
           :                  //  Else (a>=b):
            a-1,              //   Start at `a-1` instead
           i->                //  In every iteration:
              b<a?            //   If `b` is smaller than `a`:
                  i-1         //    Decrement once
                 :            //   Else (b>=a)
                  i+1)        //    Increment once instead
  .limit(a<b?                 //  If `a` is smaller than `b`:
             b+~a             //   Do `b-a-1` amount of iterations
         :a>b?                //  Else-if `a` is larger than `b`:
              a+~b            //   Do `a-b-1` amount of iterations
         :                    //  Else (`a` equals `b`):
          0)                  //   Make the IntStream empty
  .filter(k->{                //  Then filter this IntStream by:
    int i=k;for(;k%--i>0;);return i<2;})
                              //   Primes-check similar as above

```
> 2 votes

# Answer
# Regex (ECMAScript 2018), ~~54~~ ~~53~~ 48 bytes

```
x(?=(x+))(?<=(?=.*\b(?!\1)x+\b).*)(?!(xx+)\2+\b)

```

Try it online!

Takes its input in unary, as two strings of `x` characters whose lengths represent the two numbers, joined/separated by a `,`. Returns its output in unary as the list of matches' `\1` captures, whose lengths represent the prime numbers in the range.

*-1 byte thanks to Neil, by leaving out an unneeded ≥2 assertion*
*-5 bytes by handling ascending and descending ranges all in one go rather than separately*

```
x                 # tail -= 1; force the top end of the range to be excluded;
                  # X = tail
(?=(x+))          # Capture \1 = tail
(?<=              # Variable-length lookbehind, evaluated right-to-left:
    (?=           # Lookahead (evaluated left-to-right):
        .*\b      # Skip tail over to a word boundary, which could be the
                  # beginning or end of the string, or either side of a comma.
        (?!\1)    # Assert tail < \1, i.e. along with the word boundary
                  # assertion above, that this is the bottom end of the range,
                  # implying \1 was captured from the upper end of the range.
        x+\b      # Assert tail >= 1
    )
    .*            # Skip all the way to the beginning, then evaluate the above
)
(?!(xx+)\2+\b)    # Assert tail is not composite; tail > 1 was already asserted
                  # above, so along with that, this asserts tail is prime.

```
> 1 votes

# Answer
# Excel, 122 bytes

```
=LET(
    a,A1,
    b,B1,
    c,a>b,
    d,SEQUENCE(IF(c,a,b)-1),
    SORT(FILTER(d,(d>IF(c,b,a))*MMULT(N(MOD(d,TRANSPOSE(d))=0),d^0)=2,""),,-1^c)
)

```

Inputs in cells `A1` and `B1`.
> 1 votes

# Answer
# Charcoal, 15 bytes

```
ＩΦ…⊕⌊θ⌈θ⬤…²ι﹪ιλ

```

Try it online! Link is to verbose version of code. Takes input as a list. Explanation:

```
  …             Range from
     θ          Input list
    ⌊           Minimum
   ⊕            Incremented
       θ        To input list
      ⌈         Maximum
 Φ              Filtered where
         …      Range from
          ²     Literal integer `2`
           ι    To current value
        ⬤       All members satisfy
             ι  Outer value
            ﹪   Modulo i.e. is not divisible by
              λ Inner value
Ｉ               Cast to string
                Implicitly print each prime on its own line

```
> 1 votes

# Answer
# Python, 67 bytes

```
lambda a,b:[n for n in range(a+1,b)if all(n%m for m in range(2,n))]

```

Attempt This Online!

The challenge has now been edited to allow *either* ascending or descending ranges, so this only supports ascending.
> 1 votes

# Answer
# Jelly, 4 bytes

```
æRḟ,

```

A dyadic Link that accepts the one bound on the left and the other bound on the right and yields a list of primes strictly between the bounds.

**Try it online!**

### How?

```
æRḟ, - Link: integer, A; integer, B
æR   - inclusive prime range -> list of primes between A and B, inclusive
   , - pair -> [A, B]
  ḟ  - filter discard -> list of primes between A and B, exclusive

```
> 1 votes

# Answer
# Thunno, \\$5\log\_{256}(96)\approx\\$ 4.12 bytes

```
:ZTgN

```

Attempt This Online! Takes the inputs in reverse order.

#### Explanation

```
:ZTgN # Inputs: x and y
:     # Push [x..y)
 ZT   # Remove first item
   gN # Filter for primes

```
> 0 votes

# Answer
# Mathematica (Wolfram Language), 61 Bytes

I'm new at this, but I thought this is a good problem to practice on.

```
Select[Range[First[Sort[{##}]]+1,Last[Sort[{##}]]-1],PrimeQ]&

```

Try it out online

This is a functional implementation, which takes a list of two numbers, orders them, and generates all integers in the open interval (input 1, input 2). Then the select function picks out all the prime elements of that interval.

I'll keep thinking about how to shorten this code.

EDIT: Added all the test cases on tio.run, and implemented Range function.
> 0 votes

---
Tags: code-golf, primes
---


title: Elevator movement order

text:
# Question
Title: Elevator movement order
There is a building with an infinite number of floors and you are the only passenger in an elevator which can lift an infinite number of people. You are going home, but before the elevator gets to your floor, the elevator stops at another floor to allow people to enter the elevator and input their destination floors. Your program should handle the floor order correctly

---

You will be given 3 inputs (the order of input doesn't matter but you need to specify the expected order of inputs):

* Integer - The number of the floor where the people entered the elevator
* Integer - Your destination floor
* Array of integers - The destination floors of entered people

You must output an array of integers with the numbers of floors (including yours) ordered correctly

The correct order is this order, where first the floors that are in the direction of your movement go in an ordered order, and then the floors that are in the direction opposite to yours go in reverse order

* The floor where the people entered is the floor where elevator already stopped so this floor should not be in the order of future destinations (output array)
* There will not be any duplicates in the input array
* Your destination floor will not be in the input array

For example let's say that elevator stopped at the ground floor, your destination is 3rd floor and people entered `[4,-2,-5,2,-4,1,5]`

So the output of must be `[1,3,4,5,-2,-4,-5]`

**Test cases:** (feel free to add more test cases)

```
0, 3, [4,-2,-5,2,-4,1,5] --> [1,2,3,4,5,-2,-4,-5]

0, -3, [4,-2,-5,2,-4,1,5] --> [-2,-3,-4,-5,1,2,4,5]

5, 10 [1,3,7,9,11,-3,-10] --> [7,9,10,11,3,1,-3,-10]

```

The shortest code in each programming language wins!

# Answer
# Python 3, ~~65~~ ~~64~~ ~~62~~ 61 bytes

```
lambda s,m,a:sorted([m]+a,key=lambda x:(x>s)*(s-m)-(s-x)**-2)

```

Try it online!

I think this may not work due to floating point inaccuracy once you reach a certain floor, since values that are too large eventually will round to the same value. Not sure what can fix that though

I reread the rules and saw there will never be duplicates so -1 byte

making the function anonymous; -2 bytes

-1 byte thanks to xnor's suggestion using `**-2` instead of `1/abs`
> 8 votes

# Answer
# , 47 bytes

```
\(e,d,l,m=c(d,l))m[order(!(m<e)-(e<d),(m-e)^2)]

```

Attempt This Online!

Approach copied from Jonah's answer \- upvote that one!

---

Previously: **, 56 bytes**

```
\(e,d,l,u=e<d,`+`=sort)c(c(d,l[i<-!(l>e)-u])+!u,l[!i]+u)

```

Attempt This Online!

Uses the `decreasing` argument of `sort` to control sorting order.
> 6 votes

# Answer
# , 71 61 59 bytes

*-10 bytes thanks to pajonk, -2 thanks to Dominic*

```
\(x,y,z,i=sort(c(z,y)))c(i[i>x&y>x],rev(i[i<x]),i[i>x&y<x])

```

Attempt This Online!
> 4 votes

# Answer
# , 29 27 bytes

```
}:@,([/:(~:&*-/),.(|@-{:))]

```

Try it online!

* Sorts by:
    + First: Are you in the same direction as start - destination, as a 0 1.
    + Then: Absolute distance from start
> 4 votes

# Answer
# Haskell, 89 bytes

```
import Data.List
g z|z=id;g _=flip;f x y v|(a,b)<-span(<x)$sort$y:v=g(x<y)(++)b$reverse a

```

Attempt This Online!
> 3 votes

# Answer
# JavaScript (ES6), 62 bytes

Expects `(stopFloor, myFloor, array)`.

```
(p,q,a)=>[...a,q].sort((a,b)=>((a<p)-(b<p))*(q-p)+(a-p)/(a-b))

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 17 bytes

```
ïš.¡›}ε{¹I‹N^iR]˜

```

Inputs in the order `myDestinationFloor, list, startFloor`.

Try it online or verify all test cases.

**Explanation:**

```
ï              # Explicitly cast the first (implicit) input to an integer
 š             # Prepend this first input-integer to the second (implicit) input-list
  .¡           # Group the integers in the list by:
    ›          #  Check if the third (implicit) input is larger than the current integer
   }ε          # After the group-by: map over the pair of lists:
     {         #  Sort the integers in the current group in ascending order
      ¹I‹      #  Check if the first input is smaller than the third input
         N^    #  Bitwise-XOR it with the 0-based map-index
           i   #  If this is truthy:
            R  #   Reverse the list to a descending order
    ]          # Close both the if-statement and map
     ˜         # Flatten this pair of lists to a single list
               # (after which the result is output implicitly)

```

Two notes:

1. The cast to integer `ï` is necessary for the sort `{`. Without it, the input would be added as a stringified integer, and the sort would put it incorrectly after all the other integers in its group.
2. The bitwise-XOR `^` is to determine whether we need to reverse the list to a descending sorted group, which will apply as follows:

| `¹I‹` (first input \< third input?) | `N` (is it the second iteration of the pair of lists?) | `iR` (reverse it?) |
| --- | --- | --- |
| truthy | 0 | yes |
| truthy | 1 | no |
| falsey | 0 | no |
| falsey | 1 | yes |
> 3 votes

# Answer
# Charcoal, 34 bytes

```
⊞ζηＷ⁻ζυ⊞υ⌊ι≔⮌Φυ‹ιθζＩ⎇‹ηθ⁺ζ⁻υζ⁺⁻υζζ

```

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

```
⊞ζη

```

Add your destination floor to the list.

```
Ｗ⁻ζυ⊞υ⌊ι

```

Sort all of the floors in ascending order.

```
≔⮌Φυ‹ιθζ

```

Extract the floors below your starting floor and reverse them.

```
Ｉ⎇‹ηθ⁺ζ⁻υζ⁺⁻υζζ

```

Remove them from the sorted list of floors and then concatenate them to either the beginning or the end depending on your direction of travel.
> 3 votes

# Answer
# MATL, 20 bytes

```
h!ti-tZSt0)=~w|h&XS)

```

Try it out at MATL Online

Input order is array of destinations, your destination, and the initial floor

**Explanation**

```
          % Implicitly grab input
h!        % Append your desired floor with the floors of everyone else
t         % Duplicate this
i-        % Subtract the initial floor
t         % Duplicate this delta
ZSt0)=~   % Compare the sign of our target floor with the sign of everyone else
          % and invert so same direction as us == 0, otherwise == 1
w         % Flip the top of the stack to get the deltas again
|         % Compute the absolute value to get the distance
h         % Horizontally concatenate the sign-agreement array with
          % the array of distances
&XS       % Sort the rows and retrieve the row indexes
)         % Index into our original array of all destinations
          % Implicitly display the result

```
> 2 votes

# Answer
# Arturo, ~~55~~ 53 bytes

```
$[g,d,a][arrange a++d'x->*(x<g)?->1->9(g-d)-^g-x 0-2]

```

Try it

Port of Bob th's Python answer.

-2 bytes thanks to a suggestion by xnor.
> 2 votes

# Answer
# Ruby, ~~58 57~~ 56 bytes

```
->a,b,l{(l<<b).sort_by{|x|x>a ?x-a:l.sort[a>b ?0:-1]-x}}

```

Try it online!

### How it works

Sort all floors above the current in ascending order, then all the floors below in descending order, then put the 2 arrays together in the right order.

This is done by "shifting" the floor numbers, if we are going up, then the floors below current get a higher number in reverse order (starting from max floor + 1 for the highest floor below current). If we are going down, then the floors below get a lower number, also in reverse order (from min floor + 1 for the highest floor below current).
> 2 votes

# Answer
# Wolfram Language (Mathematica), 99 bytes

```
Join@@({s,m,a}={##};t={SortBy[#1,(s-#)&],#2}&@@SplitBy[Sort@Append[a,m],#>s&];If[m>s,Reverse@t,t])&

```

Try it online!

Need to be golfed =(
try to do it later...
> 1 votes

---
Tags: code-golf
---


title: Harmonic divisor numbers

text:
# Question
Title: Harmonic divisor numbers
Consider the \\$4\\$ divisors of \\$6\\$: \\$1, 2, 3, 6\\$. We can calculate the harmonic mean of these numbers as

$$\frac 4 {\frac 1 1 + \frac 1 2 + \frac 1 3 + \frac 1 6} = \frac 4 {\frac {12} 6} = \frac 4 2 = 2$$

However, if we take the \\$6\\$ divisors of \\$12\\$ (\\$1, 2, 3, 4, 6, 12\\$) and calculate their harmonic mean, we get

$$\frac 6 {\frac 1 1 + \frac 1 2 + \frac 1 3 + \frac 1 4 + \frac 1 6 + \frac 1 {12}} = \frac 6 {\frac {28} {12}} = \frac {18} {7}$$

Ore numbers or harmonic divisor numbers are positive integers \\$n\\$ where the harmonic mean of \\$n\\$'s divisors is an integer, for example \\$6\\$. They are A001599 in the OEIS.

The first few Ore numbers are

```
1, 6, 28, 140, 270, 496, 672, 1638, 2970, 6200, 8128, 8190, ...

```

Point of interest: this sequence contains all the perfect numbers (see Wikipedia for a proof).

---

This is a standard challenge. You may choose which of the following three options to do:

* Take a positive integer \\$n\\$ and output the first \\$n\\$ Ore numbers.
* Take a positive integer \\$n\\$ and output the \\$n\\$th Ore number.
    + You may use 0-indexing (so non-negative input) or 1-indexing, your choice
* Take no input, and output the never ending list of Ore numbers.

Note that your answer cannot fail due to floating point errors.

This is , so the shortest code in bytes wins.

# Answer
# Factor \+ `lists.lazy math.primes.factors math.unicode`, <sup>~~69~~</sup> 65 bytes

```
[ 1 lfrom [ divisors [ length 1 ] keep n/v Σ mod 0 = ] lfilter ]

```

Try it online!

It's a quotation that returns an infinite lazy list of the harmonic divisor numbers.

## Explanation

* `1 lfrom` an infinite lazy list of natural numbers
* `[ ... ] lfilter` select numbers for which the quotation returns `true`
* `divisors` get the divisors of a number (e.g. `6 divisors` -\> `{ 1 2 3 6 }`)
* `[ length 1 ] keep` (e.g. `{ 1 2 3 6 } [ length 1 ] keep` -\> `4 1 { 1 2 3 6 }`)
* `n/v` divide number by vector (e.g. `1 { 1 2 3 6 } n/v` -\> `{ 1 1/2 1/3 1/6 }`)
* `Σ` take the sum
* `mod 0 =` is it a divisor?
> 4 votes

# Answer
# , ~~55~~ 52 bytes

*-3 bytes thanks to @Dominic van Essen.*

```
while(F<-F+1)(1/mean(1/(y=1:F)[!F%%y]))%%1||print(F)

```

Try it online!

Prints Ore numbers infinitely.
> 4 votes

# Answer
# Raku, 46 bytes

```
grep {{@_%%sum 1 X/@_}(grep $_%%*,1..$_)},^∞

```

Try it online!

This is a lazy infinite sequence of the harmonic divisor numbers.
> 4 votes

# Answer
# Jelly, 9 bytes

```
ÆDpWSḍ/µ#

```

Try It Online!

This is horribly scuffed because I couldn't figure out how to get it working with precision. I had the same idea as ovs it turns out, but `ÆDÆmḍµ#` fails due to precision issues.

I honestly hate how this is written.

```
ÆDpWSḍ/µ#    Main Link
       µ#    nfind; return first n values satisfying:
ÆD           divisors of n
  p          cartesian product with
   W         [n] (returns [[a, n], [b, n], ...])
    S        sum (returns [divisor sum, divisor count * n])
     ḍ/      reduce by divisibility check

```
> 3 votes

# Answer
# Pari/GP, 42 bytes

```
for(n=1,oo,numdiv(n)*n%sigma(n)||print(n))

```

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~42~~ 40 bytes

-2 bytes thanks to att!

```
Do[Mean@Divisors@n∣n&&Print@n,{n,∞}]

```

Try it online!
> 3 votes

# Answer
# Charcoal, 37 bytes

```
Ｎθ≔⁰ηＷθ«≦⊕η≔Φ⊕η∧κ¬﹪ηκζ¿¬﹪×ηＬζΣζ≦⊖θ»Ｉη

```

Try it online! Link is to verbose version of code. Outputs the 1-indexed `n`ᵗʰ Ore number. Explanation:

```
Ｎθ

```

Input `n`.

```
≔⁰η

```

Start looking for Ore numbers greater than zero.

```
Ｗθ«

```

Repeat until the `n`ᵗʰ number has been found.

```
≦⊕η

```

Try the next integer.

```
≔Φ⊕η∧κ¬﹪ηκζ

```

Get its factors.

```
¿¬﹪×ηＬζΣζ

```

If the harmonic mean is an integer, then...

```
≦⊖θ

```

Decrement the count of remaining Ore numbers to find.

```
»Ｉη

```

Print the found Ore number.
> 2 votes

# Answer
# Ruby, ~~71~~ 56 bytes

```
1.step{|n|k=0;(1..n).count{|x|n%x<1&&k+=1r/x}%k>0||p(n)}

```

Try it online!

* Saved 15 thanks to @G B lots of golfs

Outputs the sequence indefinitely.
> 2 votes

# Answer
# Jelly, 9 bytes

```
1Æd×ọÆsƲ#

```

Try it online!

More boring than the other answer:

```
             Implicit input: an integer z.
1      Ʋ#    Count up from 1, finding z numbers for which...
 Æd×           divisor_count(n) × n
    ọ          is divisible by
     Æs        divisor_sum(n).

```
> 2 votes

# Answer
# Core Maude, 248 bytes

```
mod H is pr LIST{Rat}. ops o h : Rat ~> Rat . var A B C D : Rat . eq o(A)= o(2
A). eq o(s A 0)= A . eq o(A s B)= o(s A(B + ceiling(frac(h(A A 0 0))))). eq h(A
s B C D)= h(A B(0 ^(A rem s B)/ s B + C)(0 ^(A rem s B)+ D)). eq h(A 0 C D)=
D / C . endm

```

The result is obtained by reducing the `o` function with the zero-indexed input \\$n\\$.

### Example Session

```
Maude> red o(0) .  --- 1
result NzNat: 1
Maude> red o(1) .  --- 6
result NzNat: 6
Maude> red o(2) .  --- 28
result NzNat: 28
Maude> red o(3) .  --- 140
result NzNat: 140
Maude> red o(4) .  --- 270
result NzNat: 270
Maude> red o(5) .  --- 496
result NzNat: 496
Maude> red o(6) .  --- 672
result NzNat: 672
Maude> red o(7) .  --- 1638
result NzNat: 1638
Maude> red o(8) .  --- 2970
result NzNat: 2970
Maude> red o(9) .  --- 6200
result NzNat: 6200
Maude> red o(10) .  --- 8128
result NzNat: 8128
Maude> red o(11) .  --- 8190
result NzNat: 8190

```

### Ungolfed

```
mod H is
    pr LIST{Rat} .

    ops o h : Rat ~> Rat .

    var A B C D : Rat .

    eq o(A) = o(2 A) .
    eq o(s A 0) = A .
    eq o(A s B) = o(s A (B + ceiling(frac(h(A A 0 0))))) .

    eq h(A s B C D) = h(A B (0 ^ (A rem s B) / s B + C) (0 ^ (A rem s B) + D)) .
    eq h(A 0 C D) = D / C .
endm

```

Maude has built-in support for rational arithmetic, so we just compute the harmonic mean of the divisors with `h`. Then, `ceiling(frac(h(...)))` will be `0` if `h(...)` is a natural number or `1` otherwise. Also, note that in Maude `0 ^ 0 == 1` and `0 ^ X = 0` for `X =/= 1`.
> 2 votes

# Answer
# Stax, 11 bytes

```
¡♪♫ö╪ü♣↕¥Vv

```

Run and debug it

Runs an infinite loop with no input.
> 2 votes

# Answer
# Zephyr, 151 bytes

```
set n to 1
while 1=1
set s to 0
set c to 0
for d from 1to n
if(n mod d)=0
set s to(/d)+s
inc c
end if
next
if((c/s)mod 1)=0
print n
end if
inc n
repeat

```

Try it online! Uses the output-infinitely strategy; you'll need to kill the program before 60 seconds in order to see any output.

### Ungolfed

```
# Start from 1
set num to 1
# Loop forever
while true
  # Calculate the sum of the reciprocals of the divisors
  # and also the total number of divisors
  set reciprocalSum to 0
  set divisorCount to 0
  for divisor from 1 to num
    if (num mod divisor) = 0
      set reciprocalSum to reciprocalSum + (/ divisor)
      inc divisorCount
    end if
  next
  # Print the number if the divisor count divided by the
  # divisor-reciprocal sum is an integer
  if ((divisorCount / reciprocalSum) mod 1) = 0
    print num
  end if
  # Go to the next number
  inc num
repeat

```
> 2 votes

# Answer
# Pyt, 22 bytes

```
1`ĐðĐĐΠ⇹/Ʃ⇹Π|?ŕĐƥ:ŕ;⁺ł

```

Try it online!

Prints Ore numbers forever.

```
1                              Push 1
 `                   ł         Do... while top of stack is truthy
  Đ                            Đuplicate
   ð                           Get list of ðivisors
    ĐĐ                         Đuplicate twice
      Π                        Get product
       ⇹                       Swap top two elements on stack
        /                      Divide
         Ʃ                     Ʃum
          ⇹                    Swap top two elements
           Π|?                 Does the sum divide the product cleanly?
              ŕĐƥ              If so, ŕemove the boolean, Đuplicate, and ƥrint
                 :ŕ            Otherwise, ŕemove the boolean
                   ;⁺          Either way, increment

```
> 2 votes

# Answer
# Vyxal 2.6.1, 5 bytes

```
≬KṁḊȯ

```

Try it Online!

This doesn't work in 2.4 because 2.6 uses sympy rationals to store non-integers. Essentially a port of hyper's hypothetical Jelly answer.

## Explained

```
≬KṁḊȯ
≬     # The next three elements as a function, taking single argument n:
 K    #    divisors of n
  ṁ   #    the average of that
   Ḋ  #    does that divide n?
    ȯ # First input numbers that satisfy the above function.

```
> 1 votes

# Answer
# JavaScript (V8), 63 bytes

Prints the sequence forever.

```
{for(n=0;;s%t||print(n))for(k=++n,t=s=0;k;)n%k--||(s+=n,t-=~k)}

```

Try it online!
> 1 votes

# Answer
# MathGolf, 13 bytes

```
î∙─‼Σ£î*\÷╛p∟

```

Outputs indefinitely.

Try it online. (You do have to manually cancel it during runtime to see output apparently, before it times out after 60 seconds..)

**Explanation:**

```
            ∟  # Do-while true without popping:
î              #  Push the 1-based loop-index
 ∙             #  Triplicate it
  ─            #  Pop the top, and get a list of its divisors
   ‼           #  Apply the following two commands separately:
    Σ          #   Sum the divisors-list
     £         #   Get the length of the divisors-list
      î*       #  Multiply the length by the 1-based loop-index
        \      #  Swap the top two values on the stack
         ÷     #  Check that the length*î is divisible by the sum
          ╛    #  If this is truthy:
           p   #   Pop the remaining copy of the index, and print it

```
> 1 votes

# Answer
# Python 3, 79 bytes

```
n=0
while 1:n+=1;a=[i for i in range(1,n+1)if n%i<1];n*len(a)%sum(a)or print(n)

```

Try it online!

Outputs indefinitely.
> 1 votes

# Answer
# Husk, 9 bytes

```
fo§¦ṁ\LḊN

```

Try it online! (header outputs the first few elements to avoid timing-out)

```
         N  # from the infinite list of integers
fo          # output those for which
     ṁ\     # the sum of the reciprocals of their divisors
  §¦        # exactly divides
       LḊ   # the length (number) of their divisors

```
> 1 votes

# Answer
# Scala, 111 bytes

```
Stream.iterate(1:BigInt)(_+1)filter{n=>val d=n to(1,-1)filter(n%_<1)
val p=d.product
p*d.size%d.map(p./).sum<1}

```

Try it online!

Returns an infinite `Stream`.

## Scala, 92 bytes

```
Stream from 1 filter{n=>val d=1 to n filter(n%_<1)
val p=d.product
p*d.size%(0/:d)(_+p/_)<1}

```

Try it online!

This one uses normal `Int`s, evading some of the boilerplate above, but it only generates the first three elements correctly due to integer overflows.
> 1 votes

# Answer
# Python 3, 94 bytes

```
v=0
while 1:p=q=1;v+=1;-~len([(p:=p*d+q,q:=q*d)for d in range(2,v+1)if v%d<1])*q%p or print(v)

```

Try it online!

Outputs indefinitely. This is otherwise like (my edit to) @Jitse's answer, but computes the sum of the reciprocals `p/q` exactly as a pair of (big)ints `(p,q)`.
> 1 votes

# Answer
# Nibbles, 8.5 bytes

```
|,~~%*,;|,$~%@$@+

```

Attempt This Online!
> 1 votes

---
Tags: code-golf, sequence, number-theory, rational-numbers
---


# Question
Title: Length of Binary as Base 10 [OEIS A242347]
Computers like binary. Humans like base 10. Assuming users are humans, why not find the best of both worlds? Your task is to find the first `n` terms in the sequence A008559 where each term is the binary representation of the previous number interpreted as a base 10 number.

## Input

An integer greater than 0. Note that the first value of A008559 is 2.

## Output

Just to make it a little more readable, the output should be the number of digits in the Nth term of A008559, which is A242347. Invalid inputs can output whatever, standard rules apply.

## Scoring

This is so shortest bytecount wins, no standard loopholes etc...

## Test Cases

```
2 -> [1,2]
5 -> [1,2,4,10,31]
10 -> [1,2,4,10,31,100,330,1093,3628,12049]
20 -> [1,2,4,10,31,100,330,1093,3628,12049,40023,132951,441651,1467130,4873698,16190071,53782249,178660761,593498199,1971558339]

```

# Answer
# Vyxal `l`, ~~8~~ ~~7~~ 5 bytes

```
2?(ΠE

```

Try it Online!

Outputs nth term

## Explained

```
2?(ΠE
2      # Push 2 to the stack
 ?(    # Input times:
   ΠE  #   push int(binary representation of top of stack)
       # the `l` flag pushes the length of the top of the stack

```

## Old 7 byter, outputs infinite sequence

```
2‡ΠEḞvL

```

Try it Online!

## Explained

```
2‡ΠEḞẎvL
2‡  Ḟ    # an infinite generator that gets its next term by:
  ΠE     #   converting its previous term to binary and casting to int
      vL # lengths of every item

```
> 4 votes

# Answer
# Ruby, ~~38~~ ~~33~~ 25 bytes

```
a=2;loop{p /$/=~a="%b"%a}

```

Attempt This Online! Outputs the sequence indefinitely starting from 2.

Thanks for a whopping -13 bytes from a collective effort by south and Dingus.
> 7 votes

# Answer
# Husk, ~~9~~ 9 bytes

```
¡o§,ḋLd;2

```

Try it online!

Outputs the infinite sequence.

---

The previous version (also 9 bytes when outputting the infinite sequence) was `moLd¡odḋ2`, but I've cleaned this up at the request of lyxal, who considered it too odd due to the moLd in it.

```
         2 # starting with 2
     ¡     # construct an infinite sequence
      o    # by repeatedly applying 2 functions:
        ḋ  #   convert to binary digits
       d   #   convert from base-10 digits
 m         # now map over this infinite list
  o        # using 2 functions:
   L       #   length of
    d      #   base-10 digits

```
> 6 votes

# Answer
# Fig, \\$8\log\_{256}(96)\approx\\$ 6.585 bytes

```
eLG2'_Ob

```

Try it online!

Port of Vyxal
> 5 votes

# Answer
# K (ngn/k), 14 bytes

```
{#$x(10/2\)/2}

```

Try it online!

Outputs the nth element.

Unfortunately, this can only do the first 3 elements because it's written in C, so overflow happens very quickly.
> 5 votes

# Answer
# Factor, 35 bytes

```
2 [ >bin dup length . dec> t ] loop

```

Prints the infinite sequence starting with 2. Times out on TIO, but here's a screenshot using the debugger to step through some of the starting iterations:
> 4 votes

# Answer
# Sequences, \\$9 \log\_{256}(96)\approx\\$ 7.4 bytes

```
2HE2hBnHz

```

### Explanation

```
2HE2hBnHz
  E        // Infinite sequence
2H         // Starting with 2
           // For each term:
   2hB     //   Convert to binary
      n    //   Interpret as integer
       H   //   And use this as the next term
        z  //   Get the length and output implicitly

```
> 4 votes

# Answer
# Python, ~~56 47~~ 40 bytes

* -9 thanks to friddo.
* -7 thanks to loopy walt.

Outputs the infinite sequence, starting from 2. (Note: apparently this is fine)

```
i=2
while i:=f"{int(i):b}":print(len(i))

```

Attempt This Online!

---

# Python, ~~66~~ 59 bytes

* -7 thanks to loopy walt.

Suggested by friddo. Returns the first n terms.

```
lambda n,i=2:[1]+[len(i:=f"{int(i):b}")for _ in range(1,n)]

```

Attempt This Online!

---

# Python, ~~74~~ 69 bytes

* -5 thanks to loopy walt.

Returns the nth term.

```
lambda n,i=2:len((['1']+[(i:=f"{int(i):b}")for _ in range(n-1)])[-1])

```

Attempt This Online!
> 3 votes

# Answer
# C (gcc), 67 bytes

```
q;b;v;f(n){for(v=2;n--;v=q)for(b=q=0;v;v/=2)q+=v%2*exp10(b++);q=b;}

```

Try it online!

Inputs \\$1\\$-based \\$n\\$.
Returns the \\$n^{\text{th}}\\$ element starting with \\$a(1) = 2\\$.
> 3 votes

# Answer
# Haskell, ~~75~~ 63 bytes

```
g 2
g x=length(show$f x):g(f x)
f 0=0
f n=f(div n 2)*10+mod n 2

```

Try it online!

* Thanks to @Sʨɠɠan for saving 2 Bytes

*f n* returns a (decimal binary, length) tuple
> 3 votes

# Answer
# Pyth, 10 bytes

```
L.BsbmlyF2

```

Test suite

Prints the first \\$n\\$ terms.

The `m` can be omitted to instead print \\$a(n)\\$, where \\$a(0)=2\\$.
> 3 votes

# Answer
# APL (dzaima/APL), 19 bytes

```
{≢⍕(10⊥2∘⊥⍣¯1)⍣⍵⊢2}

```

Try it online!

Due to limits, this can also only output the first 5 elements.

This works in Dyalog too, but can only output the first 3 elements there.
> 3 votes

# Answer
# PARI/GP 55 bytes

```
f(n)=k=2;d=digits;while(n--,k=fromdigits(d(k,2)));#d(k)

```

Stack of 8 GBytes overflows for n=18.
> 3 votes

# Answer
# Raku, ~~16~~ 30 bytes

```
map *.chars,(2,+*.base(2)...*)

```

Try it online!

An expression for the lazy, infinite sequence of numbers.
> 3 votes

# Answer
# , 18 bytes

```
[:#@":10x&(#.#:)&2

```

Attempt This Online!

-2 thanks to Jonah!
> 3 votes

# Answer
# Jelly,  ~~8~~  7 bytes

```
‘ḊḌB$\Ẉ

```

A monadic Link that accepts a positive integer, \\$n\\$, and yields a list of the first \\$n\\$ terms.

**Try it online!**

### How?

Performs each conversion step in the opposite order as it avoids the need to get lists again at the end.

Uses a reduce that only uses the left item at each step, starting with a list of length \\$n\\$ that starts with a \\$2\\$ as it saves a byte over collecting up \\$n-1\\$ times starting with a \\$2\\$.

```
‘ḊḌB$\Ẉ - Link: integer, n
‘       - increment (n) -> n+1
 Ḋ      - dequeue ([1..n+1]) -> [2..n+1]
     \  - reduce by:
    $   -   last two links as a monad - i.e. f(left):
 Ḍ      -     convert from decimal e.g. 2 -> 2     or [1,0,1,0] -> 1010
  B     -     convert to binary    e.g. 2 -> [1,0] or 1010 -> [1,1,1,1,1,1,0,0,1,0]
      Ẉ - length of each

```
> 2 votes

# Answer
# JavaScript (Node.js), 54 bytes

*-3 bytes thanks to @Sʨɠɠan*

Prints the sequence indefinitely, starting at \\$2\\$ (as now allowed by the OP).

```
for(n=2;;console.log(n.length))n=BigInt(n).toString(2)

```

Try it online!
> 2 votes

# Answer
# Nibbles, 7.5 bytes (15 nibbles)

```
.`.2`@~``@$,`p

```

```
   2            # start with 2
 `.             # iterate while unique:
       ``@$     #   convert to bits
    `@~         #   and convert to base 10
.               # now, map over this infinite list
           ,    #   get lengths of
            `p  #   string representations

```
> 2 votes

# Answer
# sclin, 21 bytes

```
"2""2X>b >S"itr"len"map

```

Try it here! Returns an infinite list.

For testing purposes (use `-i` flag if running locally):

```
; 10tk >A
"2""2X>b >S"itr"len"map

```

## Explanation

Prettified code:

```
"2" ( 2X>b >S ) itr \len map

```
* `"2" ( ... ) itr` generate infinite list starting from 2...
    + `2X>b` to binary
    + `>S` to string
* `\len map` get lengths of each element
> 2 votes

# Answer
# Charcoal, 17 bytes

```
≔2θＦＮ«⟦ＩＬθ⟧≔⍘Ｉθ²θ

```

Try it online! Link is to verbose version of code. As we are outputting A242347, which starts with `1`, so does this version. Explanation:

```
≔2θ

```

Start with `2`.

```
ＦＮ«

```

Repeat `n` times.

```
⟦ＩＬθ⟧

```

Output its length on its own line.

```
≔⍘Ｉθ²θ

```

Cast it to decimal, then convert it to binary as a string.
> 2 votes

# Answer
# Retina 0.8.2, 45 bytes

```
.+
$*:2
{`:\d+
$*B
+`(B+)\1
$1A
AB
B
}T`L`d
.

```

Try it online! Outputs the 0-indexed `n`th term. Link includes test cases for `0` to `3` as higher values are too slow. Explanation:

```
.+
$*:2

```

Convert the input to unary as a number of `:`s and suffix a `2` for the zeroth value.

```
{`
}`

```

Repeat until the nth value has been found.

```
:\d+
$*B

```

If more terms are needed then convert the current value into unary as a number of `B`s.

```
+`(B+)\1
$1A
AB
B

```

If there are any `B`s then convert them to binary using `B` for `1` and `A` for `0`. This is done separately to avoid corrupting the final value.

```
T`@=`d

```

Convert the "binary" to normal digits.

```
.

```

Count the number of digits in the final value.

A008559 can be obtained at a saving of 3 bytes by deleting the last line and removing the `}`.
> 2 votes

# Answer
# Pip, 10 bytes

```
Y2LaP#TB:y

```

Try It Online!

Prints the first `a` terms in the sequence starting with 2, where `a` is the argument input.

```
Y2LaP#TB:y      ; a = input
Y2              ; Set y = 2
  La            ; Loop the following code "a" times...
    P#          ; Print the length of...
      TB:y      ; y treated as a decimal number converted to a binary string
                  and set y to that value

```
> 2 votes

# Answer
# cQuents, 9 bytes

```
Lb$
=2:JZ

```

Try it online!

Prints the entirely sequence infinitely starting with `1,2,4,10,31,100,330,...`

## Explanation

**First line**

```
       implicit : output the nth term if input is provided, or all terms in the sequence if no input provided
       each term in the sequence equals
L                                       length (                       )
 b                                               second line (       )
  $                                                            index

```

**Second line**

```
=2     first term in sequence is 2
  :    output the nth term in the sequence
       each term in the sequence equals
   J                                    base 2 of (                   )
    Z                                               the previous term

```
> 2 votes

# Answer
# 05AB1E, 6 bytes

Infinite sequence starting at `2`:

```
Tλb}€g

```

Try it online.

Could be the infinite sequence starting at `1` by replacing `T` with `2`: `2λb}€g` \- try it online.

Outputting the \\$n^{th}\\$ term is 6 bytes as well with either `2λèb}g` (try it online) or `2IFb}g` (try it online);
and outputting the first \\$n\\$ values is 7 bytes with either `2λ£b}€g` (try it online) or `2IFbDg,` (try it online).

**Explanation:**

```
 λ      # Start a recursive environment,
        # to output the infinite sequence
T       # Starting at a(0)=10
        # Where every following a(n) is calculated as:
        #  (implicitly push the previous term a(n-1))
  b     #  Convert it from a base-10 integer to a binary string
   }€   # After we have the infinite sequence: map over each binary string:
     g  #  Pop and push its length
        # (after which the infinite sequence is output implicitly)

```
> 2 votes

# Answer
# MathGolf, 7 bytes

```
2æhpià∟

```

Prints the infinite sequence, starting from `1`.

Try it online.

Outputting the first \\$n\\$ terms would be 8 bytes instead:

```
2kæhpià;

```

Try it online.

**Explanation:**

```
2        # Push a 2
      ∟  # Do-while true (without popping),
 æ       # using 4 characters as inner code-block:
  h      #  Push the length (without popping)
   p     #  Pop and print it with trailing newline
    i    #  Convert the binary-string to a base-10 integer
     à   #  Convert that integer to a binary-string

```

The program for the first \\$n\\$ terms is pretty similar, except that `k` pushes the input-integer; `æ` acts as a loop that many times instead of the do-while loop; and `;` discards the final binary-string after the loop, which would otherwise have been output implicitly.
> 2 votes

# Answer
# Perl 5 -Mbigint, 58 bytes

```
eval'$_=2;'.'$_=new Math::BigInt($_)->to_bin;'x$_;$_=y///c

```

Try it online!
> 2 votes

# Answer
# \>\<\>, 40 bytes

```
2:2(?v:2%$2,:1%-!
?v00.>lnao>l1)
.>a*+a1

```

Try it online

"Infinte sequence". Overflows at the 7th number.
> 2 votes

# Answer
# Gaia, 11 bytes

```
)2¤U⟪¤bd⟫⊢l

```

Try it online! or Try a test suite!

A sort of copy of the Jelly answer but in Gaia. Times out for \>= 12 I think.

## Explained

```
)2¤U⟪¤bd⟫⊢l
)            # Increment the input
 2¤          # Push 2 "under" the incremented input by pushing 2 and then swapping
   U         # Push a range [2, input + 1] to the stack
    ⟪   ⟫⊢   # Reduce that list by:
     ¤b      #   Converting the last item to binary
       d     #   And then to decimal
         l   # Get the length of the result

```
> 1 votes

# Answer
# Pyt, 8 bytes

```
2`ĐąŁƥɓł

```

Try it online!

Prints indefinitely.

```
2           push 2
 `     ł    do... while top of stack is truthy
  Đ         Đuplicate
   ą        convert to ąrray of digits
    Łƥ      ƥrint Łength
      ɓ     convert to ɓinary string (implicitly treats output as decimal number)

```
> 1 votes

---
Tags: code-golf, math, sequence
---


title: Exact Partial Sum of Harmonic Series

text:
# Question
Title: Exact Partial Sum of Harmonic Series
### Challenge

Given a positive integer `N`, output the sum of the first `N` reciprocals as an exact fraction, which is represented as a pair of integers in a consistent order representing numerator and denominator.

### Rules

* Output must be exact.
* Output should be as a pair of integers in a consistent order representing numerator and denominator.
* Using non-integer numeric types (built-in or library) is forbidden.

+ Clarification/exception: non-integer numeric types are okay if and only if all values used, computed, and returned are integers (i.e. your language uses rational numbers by default, but you only use integer arithmetic in your answer)
* Output should be as reduced as possible. (`3/2` is okay, `6/4` is not)
* Standard loopholes are forbidden.
* Submissions should work for inputs at least up to 20, or this meta, whichever is higher.

### Test Cases

```
1: 1/1
2: 3/2 (1/1 + 1/2)
3: 11/6 (1/1 + 1/2 + 1/3)
4: 25/12 etc.
5: 137/60
6: 49/20
20: 55835135/15519504
56: 252476961434436524654789/54749786241679275146400
226: 31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161/5290225078451893176693594241665890914638817631063334447389979640757204083936351078274058192000

```

### Test-Case Generation (Python 3)

```
import fractions
def f(x):
    return sum(fractions.Fraction(1,i) for i in range(1,x+1))

```

Similar to this challenge and this challenge.

Numerators are OEIS A001008, and denominators are OEIS A002805.

# Answer
# Jelly, 10 bytes

```
!:RS,!:g/$

```

Try it online!

### How it works

```
!:RS,!:g/$  Main link. Argument: n

!           Compute n!.
  R         Range; yield [1, ..., n].
 :          Divide n! by each k in [1, ..., n].
   S        Take the sum. Let's call it s.
     !      Compute n! again.
    ,       Pair; yield [s, n!].
      :g/$  Divide [s, n!] by their GCD.

```
> 9 votes

# Answer
# Python 2, ~~80~~ 79 bytes

```
D=1;N=n=0;exec"n+=1;y=N=N*n+D;x=D=D*n;"*input()
while y:x,y=y,x%y
print N/x,D/x

```

Try it online!

Prints the numerator and denominator.

Yay! MathJax support!!!! One observes:

$$\sum\_{i=1}^{n} \frac{1}{i} = \sum\_{i=1}^{n} \frac{n!}{n!i} = \frac{\sum\_{i=1}^{n} \frac{n!}{i}}{n!}$$

Then, thinking about recursion, for \\$n\\$ positive, in the `N`umerator:

$$\sum\_{i=1}^{n+1} \frac{(n+1)!}{i} = (n+1) \sum\_{i=1}^{n} \frac{n!}{i} + \frac{(n+1)!}{n+1} = (n+1) \sum\_{i=1}^{n} \frac{n!}{i} + n!$$

and one can't help think of the `D`enominator \\$n!\\$ recursively as well; thus the `exec`.

We must pay the Reduced Fraction Piper with a GCD calculation in the `while` loop; and then we're done.
> 8 votes

# Answer
# , 16 bytes

```
!(,%+.)1#.!%1+i.

```

Try it online!

### Run examples

```
f =: !(,%+.)1#.!%1+i.
f 6x
   20 49
f 20x
   15519504 55835135
f 56x
   54749786241679275146400 252476961434436524654789

```

### How it works

```
!(,%+.)1#.!%1+i.    NB. Tacit verb
            1+i.    NB. 1 to n inclusive
          !%        NB. Divide factorial by 1 to n
       1#.          NB. Sum i.e. numerator (not reduced)
!                   NB. Factorial i.e. denominator (not reduced)
 (,%+.)             NB. Divide both by GCD

```

---

## , 9 bytes, using fraction type

```
1#.1%1+i.

```

Try it online!

J gives fractions for int-int division if not divisible.
> 5 votes

# Answer
# 05AB1E, 10 bytes

```
!DIL÷O)D¿÷

```

Try it online!

Uses the same method as all other entries. Output is in the form `[denominator, numerator]`.

```
!DIL÷O)D¿÷   Full program. Let's call the input I.
!D           Push the factorial twice to the stack. STACK: [I!, I!]
  IL         Range from 1 to I. STACK: [I!, I!, [1 ... I]]
    ÷        Vectorized integer division. STACK: [I!, [I! / 1, I! / 2, ..., I! / I]]
     O       Sum. STACK: [I!, I! / 1 + I! / 2 + ... + I! / I]
      )      Wrap stack. STACK: [[I!, I! / 1 + I! / 2 + ... + I! / I]]
       D     Duplicate. STACK: [[I!, I! / 1 + ... + I! / I], [I!, I! / 1 +... + I! / I]]
        ¿    GCD. STACK: [[I!, I! / 1 + ... + I! / I], gcd(I!, I! / 1 +... + I! / I)]
         ÷   Vectorized integer division.

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), 30 bytes

```
#/GCD@@#&@{Tr[#!/Range@#],#!}&

```

Try it online!

---

## 14 bytes if built-in fractional types are allowed

```
HarmonicNumber

```

Try it online!
> 4 votes

# Answer
# Perl 6, ~~57~~ 53 bytes

```
{+($!=[*] 1..$_)/($!=($/=sum $! X/1..$_)gcd$!),$//$!}

```

Try it online!

An anonymous code block that takes an integer and returns a tuple of `denominator, numerator`.

If we were allowed to use fractional types, it would be the much simpler 32 byter:

```
{sum(map 1/*.FatRat,1..$_).nude}

```

Try it online!
> 3 votes

# Answer
# JavaScript (ES6), 60 bytes

Returns `[numerator, denominator]`.

```
f=(n,a=0,b=1)=>n?f(n-1,p=a*n+b,q=b*n):b?f(0,b,a%b):[p/a,q/a]

```

Try it online!

### How?

The method is similar to @ChasBrown's Python answer.

We first compute the unreduced numerator \\$a\\$ and unreduced denominator \\$b\\$ by starting with \\$a=0\\$ and \\$b=1\\$ and recursively doing:

$$a\gets an+b\\ b\gets bn\\ n\gets n-1$$

until \\$n=0\\$.

We save \\$(a,b)\\$ into \\$(p,q)\\$ and then compute \\$a\gets \gcd(a,b)\\$ with:

$$a\gets b\\ b\gets a \bmod b$$

until \\$b=0\\$.

We finally return the reduced numerator \\$p/a\\$ and reduced denominator \\$q/a\\$.
> 3 votes

# Answer
# Pari/GP, 34 bytes

```
n->l=[sum(i=1,n,n!/i),n!];l/gcd(l)

```

Try it online!

---

## 17 bytes if built-in fractional types are allowed

```
n->sum(i=1,n,1/i)

```

Try it online!
> 2 votes

# Answer
# Octave, 29 bytes

```
@(n)sym(sprintf('+1/%i',1:n))

```

**Try it online!**
> 2 votes

# Answer
# C++17 (gcc), 108 bytes

Only use integer arithmetic:

```
#import<random>
int f(int x,long&n,long&d){n=0;d=1;int
a;while(n=n*x+d,d*=x,a=std::gcd(n,d),n/=a,d/=a,--x);}

```

Try it online!

---

# C++17 (gcc), 108 bytes

```
#import<random>
int f(long&n){double a=0;long
d=1;while(d*=n,a+=1./n,--n);n=a*d+.5;n/=a=std::gcd(n,d);d/=a;}

```

Try it online!

Same as below, but use C++17's `std::gcd`.

---

# C++ (gcc), 109 bytes

```
#import<regex>
int f(long&n){double a=0;long
d=1;while(d*=n,a+=1./n,--n);n=a*d+.5;n/=a=std::__gcd(n,d);d/=a;}

```

Try it online!

Because C++ doesn't have native bigint support, this will definitely overflow for `n>20`.

Require:

* gcc's deprecated `import` statement.
* gcc's `std::__gcd`.
* `-O0` (I think so) otherwise the compiler will optimize out `d/=a`.
* At least 64-bit `long`.

Explanation:

* Let \\$d=n!, a=H\_n\\$.
* Round `a*d` to nearest integer by casting `a*d+.5` to `long`, and assign to `n`. Now `n/d` is the output.
* Simplify the fraction with `std::__gcd`.
> 2 votes

# Answer
# MATL, 13 bytes

```
:tptb/sht&Zd/

```

Try it on MATL Online

Same method as used in @Dennis' Jelly answer.

```
:t    % Range from 1 to n, duplicate.
pt    % Take the product of that (= factorial), duplicate that too.
b/    % Bring the range to top of stack, divide factorial by each element
sh    % Sum those. Concatenate factorial and this into a single array.
t&Zd/ % Compute GCD of those and divide the concatenated array elements by the GCD.

```

(Implicit output, prints denominator first and then the numerator.)

~~Floating point inaccuracies mean this doesn't work for n = 20, because the intermediate values are too large.~~ Looks like the test case output was a typo, this returns the same answer as the other answers for n=20.

Here's an integer type-preserving version (25 bytes) I tried in the meantime, before finding this out:

### 25 bytes, input upto 43

```
O1i:3Y%"t@*b@*b+wht&Zd/Z}

```

Try it online!

Casts the numbers to `uint64` before operating on them, does the arithmetic explicitly in a loop (without using `prod` or `sum`). More importantly, divides the partial numerators and denominators by their GCD every step along the way, at the end of each iteration. This increases the input range to allow `n` upto 43. Part of the code is based on @Chas Brown's Python answer.

Alternate (original) method using LCM instead of factorial:

### ~~16~~ 15 bytes

```
:t&Zmtb/sht&Zd/

```

Try it on MATL Online
> 2 votes

# Answer
# Stax, 11 bytes

```
ó╢Δ'åç4}ú┌7

```

Run and debug it

Explanation:

We want to calculate:

$$\sum\_{i=1}^n{\frac 1 i}$$

We now need a denominator \\$b\\$ and a list of numerators \\$a\_i\\$:

$$\sum\_{i=1}^n{\frac{a\_i}b}=\frac{\sum\_{i=1}^n{a\_i}}{b}$$

We can make \\$b=n!\\$, then we have:

\begin{align} \frac{a\_i}{n!}&=\frac 1 i&|\times n! \\ a\_i&=\frac{n!}i \end{align}

So we have:

$$\sum\_{i=1}^n{\frac 1 n}=\frac{\sum\_{i=1}^n{\frac{n!}i}}{n!}$$

```
|Fx{[/m|+L:_m Full program
|F            Factorial
  x           Push input again
   {  m       Map over range [1, n]
    [           Copy the factorial
     /          Divide factorial by current value
       |+     Sum
         L    Listify stack, top gets first element
          :_  Divide both values by gcd
            m Print each followed by newline

```
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~15~~ 12 bytes

```
⌽!(,÷∨)1⊥!÷⍳

```

Try it online!

Tacit function, taking a single argument . Saves a byte by removing the  if we're allowed to print the denominator first.

Thanks @dzaima for 3 bytes.

### How:

```
⌽!(,÷∨)1⊥!÷⍳ ⍝ Tacit function, argument will be called ⍵.
           ⍳ ⍝ Range 1..⍵
          ÷  ⍝ Dividing
         !   ⍝ the factorial of ⍵
       1⊥    ⍝ Base-1 decode, aka sum;
 !(   )      ⍝ Using that sum and the factorial of ⍵ as arguments, fork:
     ∨       ⍝ (GCD
    ÷        ⍝ dividing
   ,         ⍝ the vector with both arguments)
⌽            ⍝ reversed.

```
> 2 votes

# Answer
# Excel VBA, 141 bytes

Takes input from `[A1]` and outputs to the console.

```
s="=If(Row()>A$1,":[B:B]=s+"1,Row())":l=[LCM(B:B)]:[C:C]=s &"0,"&l &"/B1)":g=[GCD(LCM(B:B),SUM(C:C))]:?Format([Sum(C:C)]/g,0)"/"Format(l/g,0)

```

### Ungolfed and Commented

```
Sub HarmonicSum(n)
    [A1] = n                            ''  Pipe input
    s = "=IF(ROW()>A$1,"                ''  Hold the start of formulas
    [B1:B40] = s + "1,ROW())"           ''  Get series of numbers 1 to N, trailing 1s
    l = [LCM(B1:B40)]                   ''  Get LCM
    [C1:C40] = s & "0," & l & "/B1)"    ''  Get LCM/M for M in 1 to N
    g = [GCD(LCM(B1:B40),SUM(C1:C40))]  ''  Get GCD
                                        ''  Format and print output
    Debug.Print Format([Sum(C1:C40)] / g, 0); "\"; Format(l / g, 0)
End Sub

```
> 1 votes

# Answer
# dc, 87 bytes

```
?sn1dsNsD[lndlDdlNln*+sN*sD1-dsn1<M]sMln1<MlDsAlNsB[lAlB%sTlBsAlTsBlB0<G]dsGxlDlA/lNlA/

```

Try it online!

This leaves the numerator and denominator on top of the stack in that order, as allowed by this output default. Since `dc` does not have a `gcd` built-in, this utilizes the Euclidean algorithm to calculate the `gcd`.
> 1 votes

# Answer
# APL(NARS), 56 chars, 112 bytes

```
{⍵=1:⊂1 1⋄{(r s)←⍺⋄(i j)←⍵⋄m÷∨/m←((r×j)+s×i),s×j}/1,¨⍳⍵}

```

test:

```
  f←{⍵=1:⊂1 1⋄{(r s)←⍺⋄(i j)←⍵⋄m÷∨/m←((r×j)+s×i),s×j}/1,¨⍳⍵}
  f 1
1 1
  f 2
3 2
  f 3
11 6
  f 20
55835135 15519504

```

In few words reduce "sum function on 2 fraction numbers" (one fraction number is a list 2 integers) on the set:

```
1 2, 1 3,..., 1 n

```

this below seems wrong:

```
 f 56
74359641471727289 16124934538402170

```

but if i change the type of input than:

```
  f 56x
252476961434436524654789 54749786241679275146400
  f 226x
31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161 529022507845189
  3176693594241665890914638817631063334447389979640757204083936351078274058192000

```
> 1 votes

# Answer
# Pyt, 14 bytes

```
Đ!⇹ř/Đ↑⇹ƩáĐÁǤ/

```

Try it online!

Outputs `[denominator, numerator]`.

```
Đ                 implicit input; Đuplicate
 !                factorial
  ⇹               swap top two on stack
   ř              řangify
    /             divide
     Đ↑           Đuplicate; get max
       ⇹          swap top two on stack
        Ʃ         Ʃum
         á        push stack to árray
          Đ       Đuplicate
           Á      push contents of Árray to stack
            Ǥ     get ǤCD
             /    divide; implicit print

```
> 1 votes

---
Tags: code-golf, math, rational-numbers
---


title: Is it a Proth number?

text:
# Question
Title: Is it a Proth number?
A Proth number, named after François Proth, is a number that can be expressed as

$$N = k \times 2^n + 1$$

Where \\$k\\$ is an odd positive integer and \\$n\\$ is a positive integer such that \\$2^n \> k\\$. Let's use a more concrete example. Take 3. 3 is a Proth number because it can be written as

$$ 3 = (1 \times 2^1) + 1 $$

and \\$2^1 \> 1\\$ is satisfied. 5 Is also a Proth number because it can be written as

$$ 5 = (1 \times 2^2) + 1 $$

and \\$2^2 \> 1\\$ is satisfied. However, 7 is *not* a Proth number because the only way to write it in the form \\$N = k \times 2^n + 1\\$ is

$$ 7 = (3 \times 2^1) + 1 $$

and \\$2^1 \> 3\\$ is not satisfied.

Your challenge is fairly simple: you must write a program or function that, given a positive integer, determines if it is a Proth number or not. You may take input in any reasonable format, and should output a truthy value if it is a Proth number and a falsy value if it is not. If your language has any "Proth-number detecting" functions, you *may* use them.

# Test IO

Here are the first 46 Proth numbers up to 1000. (A080075)

```
3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993

```

Every other valid input should give a falsy value.

As usual, this is code-golf, so standard loopholes apply, and the shortest answer in bytes wins!

---

*Number theory fun-fact side-note:*

The largest known prime that is *not* a Mersenne Prime is \\$19249 \times 2^{13018586} + 1\\$, which just so happens to also be a Proth number!

# Answer
> 48 votes
# Jelly, 5 bytes

```
’&C²>

```

Try it online! or verify all test cases.

Let \\$\newcommand{\\&}\[\]{\text{ & }}j\\$ be a strictly positive integer. \\$j + 1\\$ toggles all trailing set bits of \\$j\\$ and the adjacent unset bit. For example, \\$10011\_{2} + 1 = 10100\_{2}\\$.

Since \\${\sim}j = -(j + 1) = -j - 1\\$, \\$-j = {\sim}j + 1\\$, so \\$-n\\$ applies the above to the bitwise NOT of \\$j\\$ (which toggles *all* bits), thus toggling all bits before the last \\$1\\$.

By taking \\$j \\& (-j)\\$ (the bitwise AND of \\$j\\$ and \\$-j\\$), all bits before and after the last set bit are nullified (since unequal in \\$j\\$ and \\$-j\\$), thus yielding the highest power of \\$2\\$ that divides \\$j\\$ evenly.

For input \\$N\\$, we want to apply the above to \\$N - 1\\$ to find \\$2^{n}\\$, the highest power of \\$2\\$ that divides \\$N - 1\\$. If \\$m = N - 1\\$, \\$-m = -(N - 1) = 1 - N\\$, so \\$(N - 1) \\& (1 - N)\\$ yields \\$2^{n}\\$.

All that's left to test is if \\$2^{n} \> k\\$. If \\$k \> 0\\$, this is true if and only if \\$(2^{n})^{2} \> k2^{n}\\$, which is true itself if and only if \\$(2^{n})^{2} \ge k2^{n} + 1 = N\\$.

Finally, if \\$(2^{n})^{2} = N = k2^{n} + 1\\$, \\$2^{n}\\$ must be odd (\\$1\\$) so the parities of both sides can match, implying that \\$k = 0\\$ and \\$N = 1\\$. In this case \\$(N - 1) \\& (1 - N) = 0 \\& 0 = 0\\$ and \\$((N - 1) \\& (1 - N))^{2} = 0 \< 1 = N\\$.

Therefore, \\$((N - 1) \\& (1 - N))^{2} \> N\\$ is true if and only if \\$N\\$ is a Proth number.

### How it works

```
’&C²>  Main link. Argument: N

’      Decrement; yield N - 1.
  C    Complement; yield 1 - N.
 &     Take the bitwise AND of both results.
   ²   Square the bitwise AND.
    >  Compare the square to N.

```

# Answer
> 48 votes
# Python, 22 bytes

```
lambda N:N-1&1-N>N**.5

```

This is a port of my Jelly answer. Test it on Ideone.

### How it works

Let \\$\newcommand{\\&}\[\]{\text{ & }}j\\$ be a strictly positive integer. \\$j + 1\\$ toggles all trailing set bits of \\$j\\$ and the adjacent unset bit. For example, \\$10011\_{2} + 1 = 10100\_{2}\\$.

Since \\${\sim}j = -(j + 1) = -j - 1\\$, \\$-j = {\sim}j + 1\\$, so \\$-n\\$ applies the above to the bitwise NOT of \\$j\\$ (which toggles *all* bits), thus toggling all bits before the last \\$1\\$.

By taking \\$j \\& (-j)\\$ (the bitwise AND of \\$j\\$ and \\$-j\\$), all bits before and after the last set bit are nullified (since unequal in \\$j\\$ and \\$-j\\$), thus yielding the highest power of \\$2\\$ that divides \\$j\\$ evenly.

For input \\$N\\$, we want to apply the above to \\$N - 1\\$ to find \\$2^{n}\\$, the highest power of \\$2\\$ that divides \\$N - 1\\$. If \\$m = N - 1\\$, \\$-m = -(N - 1) = 1 - N\\$, so \\$(N - 1) \\& (1 - N)\\$ yields \\$2^{n}\\$.

All that's left to test is if \\$2^{n} \> k\\$. If \\$k \> 0\\$, this is true if and only if \\$(2^{n})^{2} \> k2^{n}\\$, which is true itself if and only if \\$(2^{n})^{2} \ge k2^{n} + 1 = N\\$.

Finally, if \\$(2^{n})^{2} = N = k2^{n} + 1\\$, \\$2^{n}\\$ must be odd (\\$1\\$) so the parities of both sides can match, implying that \\$k = 0\\$ and \\$N = 1\\$. In this case \\$(N - 1) \\& (1 - N) = 0 \\& 0 = 0\\$ and \\$((N - 1) \\& (1 - N))^{2} = 0 \< 1 = N\\$.

Therefore, \\$((N - 1) \\& (1 - N))^{2} \> N\\$ is true if and only if \\$N\\$ is a Proth number.

Ignoring floating point inaccuracies, this is equivalent to the code `N-1&1-N>N**.5` in the implementation.

# Answer
> 10 votes
# Mathematica, ~~50~~ ~~48~~ ~~45~~ ~~40~~ ~~38~~ ~~35~~ ~~31~~ 29 bytes

Mathematica generally sucks when it comes to code golf, but sometimes there's a built-in that makes things look really nice.

```
1<#<4^IntegerExponent[#-1,2]&

```

A test:

```
Reap[Do[If[f[i],Sow[i]],{i,1,1000}]][[2,1]]

{3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993}

```

Edit: Actually, if I steal Dennis's bitwise AND idea, I can get it down to ~~23~~ ~~22~~ 20 bytes.

# Mathematica, ~~23~~ ~~22~~ 20 bytes (thanks A Simmons)

```
BitAnd[#-1,1-#]^2>#&

```

# Answer
> 10 votes
# Python 2, 23 bytes

```
lambda n:(~-n&1-n)**2>n

```

# Answer
> 8 votes
# 05AB1E, ~~14~~ 10 bytes

Thanks to **Emigna** for saving 4 bytes!

### Code:

```
<©Ó¬oD®s/›

```

Uses the **CP-1252** encoding. Try it online!.

### Explanation:

For the explanation, let's use the number **241**. We first decrement the number by one with `<`. That results into **240**. Now, we calculate the prime factors (with duplicates) using `Ò`. The prime factors are:

```
[2, 2, 2, 2, 3, 5]

```

We split them into two parts. Using `2Q·0K`, we get the list of two's:

```
[2, 2, 2, 2]

```

With `®2K`, we get the list of the remaining numbers:

```
[3, 5]

```

Finally, take the product of both. `[2, 2, 2, 2]` results into **16**. The product of `[3, 5]` results into **15**.

This test case is truthy since **16** \> **15**.

# Answer
> 7 votes
# Brain-Flak, ~~460~~ ~~350~~ ~~270~~ ~~266~~ ~~264~~ ~~188~~ 176 bytes

Try it online!

```
({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<>)

```

### Explanation

The program goes through powers of two and four until it finds a power of two greater than N-1. When it finds it it checks for the divisibility of N-1 by the power of two using modulo and outputs the result

```
({}[()])      #Subtract one from input
(((<>())))    #Put three ones on the other stack
{
 {}           #Pop the crap off the top
 ([(
  ((({}<(({}){})>){}){}) #Multiply the top by four and the bottom by two
  <>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{} #Check if the power of four is greater than N-1
}
(<{}{}>) #Remove the power of 4
<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>) #Modulo N-1 by the power of two

```

This program is not stack clean. If you add an extra 4 bytes you can make it stack clean:

```
({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)

```

# Answer
> 7 votes
# Regex (ECMAScript), ~~48~~ ~~43~~ 41 bytes

Neil's and H.PWiz's regexes (both also ECMAScript flavour) are beautiful in their own right. There is another way to do it, which by a pretty neat coincidence was 1 byte more than Neil's, and now with H.PWiz's suggested golfing (thanks!), is 1 byte ~~more~~ less than H.PWiz's.

**Warning:** Despite this regex's small size, it contains a **major spoiler**. I highly recommend learning how to solve unary mathematical problems in ECMAScript regex by figuring out the initial mathematical insights independently. It's been a fascinating journey for me, and I don't want to spoil it for anybody who might potentially want to try it themselves, especially those with an interest in number theory. See this earlier post for a list of consecutively spoiler-tagged recommended problems to solve one by one.

So **do not read any further if you don't want some advanced unary regex magic spoiled for you**. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in ECMAScript regex as outlined in that post linked above.

So, this regex works quite simply: It starts by subtracting one. Then it finds the largest odd factor, *k*. Then we divide by *k* (using the division algorithm briefly explained in a spoiler-tagged paragraph of my factorial numbers regex post). We sneakily do a simultaneous assertion that the resultant quotient is greater than *k*. If the division matches, we have a Proth number; if not, we don't.

I was able to drop 2 bytes from this regex (43 → 41) using a trick found by Grimmy that can futher shorten division in the case that the quotient is guaranteed to be greater than or equal to the divisor.

> `^x(?=(x(xx)*)\1*$)((\1x*)(?=\1\4*$)x)\3*$`

Try it online!

> ```
>
>  # Match Proth numbers in the domain ^x*$
>  ^
>  x                         # tail = tail - 1
>  (?=(x(xx)*)\1*$)          # \1 = largest odd factor of tail
>
>  # Calculate tail / \1, but require that the quotient, \3, be > \1
>  # (and the quotient is implicitly a power of 2, because the divisor
>  # is the largest odd factor).
>  (                         # \3 = tail / \1, asserting that \3 > \1
>      (\1x*)                # \4 = \3-1
>      (?=\1\4*$)            # We can skip the test for divisibility by \1-1
>                            # (and avoid capturing it) because we've already
>                            # asserted that the quotient is larger than the
>                            # divisor.
>      x
>  )
>  \3*$
>
> ```

# Answer
> 5 votes
# MATL, 9 bytes

```
qtYF1)EW<

```

Truthy output is `1`. Falsy is `0` or empty output. (The only inputs that produce empty output are `1` and `2`; the rest produce either `0` or `1`).

**Try it online!**

### Explanation

Let *x* denote the input. Let *y* be the largest power of 2 that divides *x*−1, and *z* = (*x*−1)/*y*. Note that *z* is automatically odd. Then *x* is a Proth number if and only if *y* \> *z*, or equivalently if *y*2 \> *x*−1.

```
q    % Input x implicitly. Subtract 1
t    % Duplicate
YF   % Exponents of prime factorization of x-1
1)   % First entry: exponent of 2. Errors for x equal to 1 or 2
E    % Duplicate
W    % 2 raised to that. This is y squared
<    % Is x-1 less than y squared? Implicitly display

```

# Answer
> 5 votes
# Haskell, ~~55~~ 46 bytes

```
f x=length [x|k<-[1,3..x],n<-[1..x],k*2^n+1==x,2^n>k]>0

```

Edit: Thanks to nimi, now 46 bytes

```
f x=or[k*2^n+1==x|k<-[1,3..x],n<-[1..x],2^n>k]

```

# Answer
> 5 votes
# Brachylog, 28 bytes

```
>N>0,2:N^P:K*+?,P>K:2%1,N:K=

```

Try it online!

Verify all testcases at once. (Slightly modified.)

### Explanation

Brachylog, being a derivative of Prolog, is very good at proving things.

Here, we prove these things:

```
>N>0,2:N^P:K*+?,P>K:2%1,N:K=

>N>0                           input > N > 0
     2:N^P                     2^N = P
         P:K*+?                P*K+1 = input
                P>K            P > K
                  K:2%1        K%2 = 1
                        N:K=   [N:K] has a solution

```

# Answer
> 4 votes
# Julia, 16 bytes

```
!x=~-x&-~-x>x^.5

```

Credits to @Dennis for the answer and some golfing tips!

# Answer
> 4 votes
# R, ~~52~~ 50 bytes

```
x=scan()-1;n=0;while(!x%%2){x=x/2;n=n+1};2^(2*n)>x

```

The program begins by dividing `N-1` (called here `P` and `x`) by `2` as long as possible in order to find the `2^n`part of the equation, leaving `k=(N-1)/2^n`, and then computes wether or not `k` is inferior to `2^n`, using the fact that `2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x`

# Answer
> 4 votes
# Regex (ECMAScript), ~~40~~ 38 bytes

*-2 bytes thanks to Deadcode*

```
^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)

```

Try it online!

Commented version:

```
# Subtract 1 from the input N
^x

# Assert N is even.
# Capture \1 = biggest power of 2 that divides N.
# Capture \2 = 2.
(?=((xx)+?)(\1\1)*$)

# Assert no odd number > \1 divides N
(?!(\1x\2*)\4*$)

```

# Answer
> 2 votes
# J, 10 bytes

```
%:<<:AND-.

```

Based on @Dennis' bitwise solution.

Takes an input `n` and returns 1 if it is Proth number else 0.

## Usage

```
   f =: %:<<:AND-.
   f 16
0
   f 17
1
   (#~f"0) >: i. 100  NB. Filter the numbers [1, 100]
3 5 9 13 17 25 33 41 49 57 65 81 97

```

## Explanation

```
%:<<:AND-.  Input: n
        -.  Complement. Compute 1-n
   <:       Decrement. Compute n-1
     AND    Bitwise-and between 1-n and n-1
%:          Square root of n
  <         Compare sqrt(n) < ((1-n) & (n-1))

```

# Answer
> 2 votes
# Retina 0.8.2, 47 bytes

```
\d+
$*
+`(1+)\1
$+0
01
1
+`.10(0*1)$
1$1
^10*1$

```

Try it online! Explanation: Given a Proth number \\$ k · 2^n + 1 \\$, you can derive two new Proth numbers \\$ (2k±1) · 2^{n + 1} + 1 \\$. We can run this in reverse until we obtain a Proth number where \\$ k = 1 \\$. This is readily performed by transforming the binary representation.

```
\d+
$*

```

Convert to unary.

```
+`(1+)\1
$+0
01
1

```

Convert to binary.

```
+`.10(0*1)$
1$1

```

Repeatedly run the Proth generation formula in reverse.

```
^10*1$

```

Match the base case of the Proth generation formula.

Edit: I think it's actually possible to match a Proth number directly against a unary number with a single regex. This currently takes me 47 bytes, 7 bytes more than my current Retina code for checking whether a unary number is a Proth number:

```
^.(?=(.+?)(\1\1)*$)(?=((.*)\4.)\3*$).*(?!\1)\3$

```

# Answer
> 2 votes
# ECMAScript Regex, 42 bytes

```
^x(?=(x(xx)*)\1*$)(?=(x+?)((\3\3)*$))\4\1x

```

Try it online! (Using Retina)

I essentially subtract 1, divide by the largest possible odd number `k`, then check that at least `k+1` is left over.

It turns out that my regex is very similar to the one Neil gives at the end of his answer. I use `x(xx)*` instead of `(x*)\2x`. And I use a shorter method to check `k < 2^n`

# Answer
> 2 votes
# Brain-Flak, 128 bytes

```
({<{({}[()]<(([{}]())<>{})<>>)}{}>{{}(<>)}{}}<><(())>){([()]{}<(({}){})>)}{}([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

```

Try it online!

I used a very different algorithm than the older Brain-Flak solution.

Basically, I divide by 2 (rounding up) until I hit an even number. Then I just compare the result of the last division with the two to the power of the number of times I divided.

## Explanation:

```
({
  # (n+1)/2 to the other stack, n mod 2 to this stack
  <{({}[()]<(([{}]())<>{})<>>)}{}>
  # if 1 (n was odd) jump to the other stack and count the one
  {{}(<>)}{}
#end and push the sum -1, with a one under it
}<>[(())])
#use the one to get a power of two
{([()]{}<(({}){})>)}{}
#compare the power of two with the remainder after all the divisions
([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

```

# Answer
> 2 votes
# Bitwise Fuckery, 56 bytes

```
,-@|~+&[>+>+<<-]>%>[<|[<+>-]>-]<<[>+<-]|+[-(>.<)>-(.>)<]

```

Try it online!

Uses the latest version of the language, in which I finally fixed the `[]` and `()` loops.

Inputs via char code. Outputs a null byte if the input is not a Proth number, outputs a non-null byte otherwise. Add the `-n` flag to output an an integer.

## How it works

Bitwise Fuckery is, unsurprisingly, an extension of brainfuck with bitwise commands, an "if zero" loop and a second tape. As demonstrated by Dennis, bitwise operations are helpful in this challenge, so I thought I'd fix up the language and give it a go.

Bitwise Fuckery's second tape has the same tape head as the first tape, and certain commands operate on the two values under the tape head on each tape. I've marked the tape heads with `(...)` in the explanation.

I'll work through the program with an example input of `5` (that's the char code of the character, not the character `5`)

```
,	# Take a byte of input
	#   Tapes: [( 5)  0   0 ...] [( 0)  0   0 ...]
-	# Decrement it
	#   Tapes: [( 4)  0   0 ...] [( 0)  0   0 ...]
@	# Swap tapes
	#   Tapes: [( 0)  0   0 ...] [( 4)  0   0 ...]
|	# Bitwise OR, copying across
	#   Tapes: [( 4)  0   0 ...] [( 4)  0   0 ...]
~+	# Bitwise NOT and increment
	#   Tapes: [(-4)  0   0 ...] [( 4)  0   0 ...]
&	# Bitwise AND
	#   Tapes: [( 4)  0   0 ...] [( 4)  0   0 ...]

[>+>+	# Copy the first cell into cells 2 and 3
 <<-]	#   Tapes: [( 0)  4   4 ...] [( 4)  0   0 ...]

>	# Move along one cell
	#   Tapes: [  0 ( 4)  4 ...] [  4 ( 0)  0 ...]
%>	# Swap the cells under the tape head and move
	#   Tapes: [  0   0 ( 4)...] [  4   4 ( 0)...]

[	# Square the value under the tape head:
 <|	# Move left and Bitwise XOR
	#   Tapes: [  0 ( 4)  4 ...] [  4 ( 4)  0 ...]
 [<+>-]	# Copy into the first cell
	#   Tapes: [  4 ( 0)  4 ...] [  4 ( 4)  0 ...]
 >-	# Move right and decrement
	#   Tapes: [  4   0 ( 3)...] [  4   4 ( 0)...]
]	# Repeat while the tape head is non-zero
	#   Tapes: [ 16   0 ( 0)...] [  4   4 ( 0)...]

<<	# Move to the first cell
	#   Tapes: [(16)  0   0 ...] [( 4)  4   0 ...]
[>+<-]	# Copy into the second cell
	#   Tapes: [( 0) 16   0 ...] [( 4)  4   0 ...]
|+	# Logical OR and increment, restoring N to the tape
	#   Tapes: [( 5) 16   0 ...] [( 4)  4   0 ...]

[	# Check that N is less than the second cell
 -	# Decrement N
	#   Tapes: [( 4) 16   0 ...] [( 4)  4   0 ...]
 (	# If zero:
  >.<	#  Output the value in the second cell
	#    Tapes: [( 4) 16   0 ...] [( 4)  4   0 ...]
 )
 >-	# Move right and decrement
	#    Tapes: [  4 (15)  0 ...] [  4 ( 4)  0 ...]
 (	# If zero:
  .>	#   Output and move right
	#    Tapes: [  4  15 ( 0)...] [  4   4 ( 0)...]
 )
 <	# Move left
	#    Tapes: [  4 (15)  0 ...] [  4 ( 4)  0 ...]
]

```

# Answer
> 2 votes
# Pyt, 7 bytes

```
Đ⁻Đ~∧²<

```

Try it online!

Port of Dennis's Jelly answer

# Answer
> 1 votes
# Java 1.7, ~~49~~ 43 bytes

*Another 6 bytes the dust thanks to @charlie.*

```
boolean g(int p){return p--<(p&-p)*(p&-p);}

```

Try it! (ideone)

~~Two ways, equally long. As with most answers here, credits go to @Dennis of course for the expression.~~

~~Taking the root of the righthand side of the expression:
```
boolean f(int p){return(p-1&(1-p))>Math.sqrt(p);}

```
Applying power of two to the lefthand side of the expression:
```
boolean g(int p){return Math.pow(p-1&(1-p),2)>p;}

```
Can shave off a single byte if a positive numeric value is allowed to represent 'truthy', and a negative value 'falsy':
```
double g(int p){return Math.pow(p-1&(1-p),2)-p;}

```
Unfortunately because of 'Narrowing Primitive Conversion' one cannot simply write this in Java and get correct results:
```
((p - 1 & (1 - p))^2) > p;

```~~

~~And any attempt to widen 'p' will lead to a compile error because bitwise operators are not supported on i.e. floats or doubles :(~~

# Answer
> 1 votes
# Maple, 100 bytes (including spaces)

```
IsProth:=proc(X)local n:=0;local x:=X-1;while x mod 2<>1 do x:=x/2;n:=n+1;end do;is(2^n>x);end proc:

```

Nicely spaced for readbility:

```
IsProth := proc( X )
    local n := 0;
    local x := X - 1;
    while x mod 2 <> 1 do
        x := x / 2;
        n := n + 1;
    end do;
    is( 2^n > x );
end proc:

```

Same idea as several others; divide X by 2 until X is no longer evenly divisible by 2, then check the criteria 2^n \> x.

# Answer
> 1 votes
# C (gcc), 29 ~~30~~ bytes

```
z;f(x){return--x<(z=x&-x)*z;}

```

Try it online!

# Answer
> 1 votes
# Hy, 37 bytes

```
(defn f[n](>(**(&(- n 1)(- 1 n))2)n))

```

Try it online!

Port of @Dennis' answer.

# Answer
> 1 votes
# Japt, ~~12~~ ~~10~~ 9 bytes

```
É&1-U)>Uq

```

Try it online!

Port of Dennis' Jelly answer again. - 1 thanks to @Shaggy.

# Answer
> 1 votes
# x86 Machine Code, 15 bytes

```
4F 89 F8 F7 D8 21 F8 0F AF C0 39 C7 19 C0 C3

```

These bytes define a function that takes the input argument (an unsigned integer) in the `EDI` register, following the standard System V calling convention for x86 systems, and it returns the result in the `EAX` register, like *all* x86 calling conventions.

In assembler mnemonics:

```
4F          dec   edi            ; input -= 1
89 F8       mov   eax, edi       ; \ temp
F7 D8       neg   eax            ; |      =
21 F8       and   eax, edi       ; /        (input & -input)
0F AF C0    imul  eax, eax       ; temp *= temp
39 C7       cmp   edi, eax       ; set CF if (input < temp)
19 C0       sbb   eax, eax       ; EAX = -CF
C3          ret                  ; return with result in EAX
                                 ;  (-1 for Proth number; 0 otherwise)

```

**Try it online!**

It's a pretty straightforward solution—and conceptually similar to MegaTom's C version. In fact, you could write this in C as something like the following:

```
unsigned IsProthNumber(unsigned input)
{
    --input;
    unsigned temp  = (input & -input);
    temp          *= temp;
    return (input < temp) ? -1 : 0;
}

```

but the machine code above is better golfed than what you'll get out of a C compiler, even when it's set to optimize for size.

The only "cheat" here is returning -1 as a "truthy" value and 0 as a "falsy" value. This trick allows the use of the 2-byte `SBB` instruction as opposed to the 3-byte `SETB` instruction.

# Answer
> 1 votes
# Thunno, \\$ 12 \log\_{256}(96) \approx \\$ 9.88 bytes

```
zt1-s1_A&2^q

```

Attempt This Online! or generate all values up to 100.

Port of Dennis's Jelly answer

#### Explanation

```
zt1-s1_A&2^q  # Implicit input
zt            # Triplicate
  1-s         # Decrement and swap
     1_       # Subtract from 1
       A&     # Bitwise AND
         2^   # Squared
           q  # Is greater than the input?

```

# Answer
> 0 votes
# Javascript ES7, 16 bytes

```
x=>x--<(-x&x)**2

```

Port of my Julia answer, which is a port of @Dennis's Jelly answer.

*Thanks @Charlie for 2 bytes saved!*

# Answer
> 0 votes
# Cjam, 11 bytes

Like many of us, piggybacking off of Dennis's excellent solution:

```
qi_(_W*&2#<

```

Try it online

# Answer
> 0 votes
# C (137 bytes)

```
int P(int N){int x=1,n=0,k=1,e=1,P=0;for(;e;n++){for(x=1,k=1;x&&x<N;k+=2){x=2<<n;x=x>k?x*k+1:0;if(x>N&&k==1)e=0;}if(x==N)P=1;}return P;}

```

Only came to read the answers after I tried it.

Considering `N=k*2^n+1` with the conditional of `k<2^n` (`k=1,3,5..` and `n=1,2,3..`

With `n=1` we have one `k` available to test. As we increase `n` we get a few more `k's` to test like so:

n=1 ; k=1

n=2 ; k=1 k=3

n=3 ; k=1 k=3 k=5 k=7

...

Iterating through those possibilities we can be sure N is not a Prouth number if for a given `n` the `k=1` number obtained is larger than N and no other iteration was a match.

So my code basically "brute-forces" its way into finding N.

After reading the other answers and realizing you can factor N-1 with 2 to find `n` and then make the conditional of `k<2^n`, I think my code could be smaller and more efficient using this method.

It was worth a try!

*Tested all numbers given and a few "non-Prouth" numbers. Function returns 1 if the number is a Prouth number and 0 if it's not.*

# Answer
> 0 votes
# C# (.NET Core), 17 bytes

```
x=>x--<(x=x&-x)*x

```

Try it online!

Port of MegaTom's C answer.

I attempted a LINQ based solution, but this was too good.

# Answer
> 0 votes
# ink, 60 bytes

```
=p(n)
~n-=n>1
~temp x=1
-(k){n%2:{n<x}->->}
~x+=x
~n=n/2
->k

```

Try it online!

Based on @DSkoog's Maple answer \- it wasn't the first of its kind to be posted, but it was the first of its kind that I saw.

### Ungolfed

```
= is_proth(number) =

/* It's easy to check if a number is one less than a Proth number.
   We take the number and divide it by 2 until we can't.
   Once we can't, we've found the smallest possible "k".
   If we also keep track of how many times we divided, we have our corresponding "2^n"
   All we have to do then is compare those
*/

~ number -= (number > 1)            // So, we first subtract one. Except this implementation won't ever halt for 0, so we don't subtract if the input is 1 (this is fine since the desired outputs for inputs 1 and 2 are the same)
~ temp power_of_two = 1             // We declare a variable to store our "2^n"
- (check)
  {
  - number % 2:                     // Once we can't divide by 2 anymore, we've found the smallest possible "k"
    {number < power_of_two}         // At that point, we print whether it's smaller than the "2^n" we found
    ->->                            // And then we return to where we were called from
  }

  ~ number = number / 2             // We keep dividing by 2 until we can't.
  ~ power_of_two += power_of_two    // and update our "2^n" as we go
-> check

```

# Answer
> 0 votes
# Stax, 6 bytes

```
öZç♫Δ¼

```

Run and debug it

---
Tags: code-golf, math, sequence, number-theory, decision-problem
---