Given a positive integer N, output the number of pairs of integers 0 <= a <= b < 2**N such that a*b >= 2**N.

Rules

You may assume that N is less than or equal to the maximum bit width for integers in your language (e.g. for C, N will not exceed 32 or 64, depending on the architecture of the machine). If your language is capable of handling arbitrary-width integers, then there is no upper bound on N.

Test Cases

1 0
2 3
3 19
4 96
5 437
6 1876
7 7804
8 31904
9 129170
10 520135
11 2088143
12 8369175
13 33512744
14 134128704
15 536681553
16 2147082274

Mego

Posted 2017-06-08T05:43:54.587

Reputation: 32 998

Note: I'm working on generating larger test cases now. My brute force approach is really slow. – Mego – 2017-06-08T05:44:14.667

@user202729 You're duplicating some pairs by not following the a <= b condition. – Mego – 2017-06-08T05:52:53.847

1Some more testcases: {0, 3, 19, 96, 437, 1876, 7804, 31904, 129170, 520135, 2088143, 8369175, 33512744, 134128704, 536681553, 2147082274, 8589086503, 34357951447} – user202729 – 2017-06-08T06:03:23.203

1Isn't there likely to be closed form formula for this problem? I must have missed something. – None – 2017-06-08T06:30:16.287

@Lembik There probably is. I don't know what it is, though. – Mego – 2017-06-08T06:31:00.593

I take it back. The answer is approximately (1/2)M^2 - M - (1/2)M ln(M) where M = 2**N. – None – 2017-06-08T07:11:38.923

Closely related: https://en.wikipedia.org/wiki/Divisor_summatory_function. There is no closed form known.

– orlp – 2017-06-08T07:32:46.440

Does ordering matter? If 2 and 3 work for example, does that count as one or two? Because that could be expressed by a=2,b=3 or a=3,b=2 – Cyoce – 2017-06-08T08:26:37.797

@Cyoce Because of the 0 <= a <= b < 2**N requirement, only (2, 3) would be considered. – Mego – 2017-06-08T08:27:26.670

@Mego right. Didn't read that part I guess – Cyoce – 2017-06-08T08:27:57.617

@Lembik: If there is, it isn't in OEIS. This was posted to math.se where there is an approximate solution but nobody has made an exact one.

– Ross Millikan – 2017-06-08T17:56:15.860

@RossMillikan Yes. Hence "I take it back." above :) The 2^{N/3} solution is pretty cool! Someone should implement that here. – None – 2017-06-08T18:02:11.427

Answers

Python 2, 75 68 bytes

n=input()
a=1<<n
s=~-a*a/2
x=y=0
while y<1:s+=y;x-=1;y=a/x-x
print s

Try it online!

This runs in O(2^n/2) operations rather than O(2ⁿ) or O(2^2·n), so it works on much larger inputs.

(Note that an even faster O(2^n/3) algorithm exists.)

1 0
2 3
3 19
4 96
5 437
6 1876
7 7804
8 31904
9 129170
10 520135
11 2088143
12 8369175
13 33512744
14 134128704
15 536681553
16 2147082274
17 8589086503
18 34357951447
19 137435198086
20 549747939928
21 2199006781125
22 8796058620153
23 35184300378083
24 140737339120148
25 562949643323164
26 2251799170232606
27 9007197921321922
28 36028794259096612
29 144115182370060793
30 576460740519709546
31 2305842984902014765
32 9223371986742908935
33 36893488044218344323
34 147573952377320833218
35 590295809922086353118
36 2361183240537767708679
37 9444732963897547996897
38 37778931859178411534913
39 151115727444080615797321
40 604462909791437463796926
41 2417851639196741979223299
42 9671406556850476410936322
43 38685626227531971124247499
44 154742504910394112443480979
45 618970019642121099638818409
46 2475880078569598086230187969
47 9903520314280668496162705117
48 39614081257127323838921620439
49 158456325028518790167805606609
50 633825300114094540502620959956
51 2535301200456417702087608942034
52 10141204801825751449333352568660
53 40564819207303170200956592005599
54 162259276829213015854387448792578
55 649037107316852746005301421147606
56 2596148429267412374169967907532731
57 10384593717069652326923914077600197
58 41538374868278615068076777292632146
59 166153499473114471992855423428749242
60 664613997892457911812090466987383188
61 2658455991569831695728843704244440740
62 10633823966279326881474627069404687424
63 42535295865117307726213589942623257944

Anders Kaseorg

Posted 2017-06-08T05:43:54.587

Reputation: 29 242

Very nice improvement! – None – 2017-06-08T10:00:38.017

2You can swap x=0;y=0 for x=y=0 – Cyoce – 2017-06-08T17:31:33.960

It would be super cool if you implemented the 2^{N/3} solution too. – None – 2017-06-08T18:04:51.807

1A full program would be 4 bytes shorter. – Dennis – 2017-06-09T04:23:59.027

Swapping some signs saves one more byte. https://tio.run/##Jc1BDoIwEEDRNXOK2QFKgyVhA53DjFqlCQ4NYOxsvHqNuv7J@1H3aZHORI2ab8uKgkFwZbn7yjZ9Xw9QxDXIjtJAESQ@dySc@XG@8oAChU/@gmVZZqFfrWpgss4JbPQ2fOC2g0RKJ3hNYfaozg7bkXRMhuyoxG0yCf6LLX@hDw

– Dennis – 2017-06-09T05:00:41.423

@Dennis Indeed, thanks! – Anders Kaseorg – 2017-06-09T05:27:02.847

Jelly, 12 10 bytes

2*ṖµṀ:«ạ¹S

Finishes the combined test cases in under 3 seconds.

Try it online!

How it works

2*ṖµṀ:«ạ¹S  Main link. Argument: n

2*          Yield 2ⁿ.
  Ṗ         Pop; yield A := [1, ..., 2ⁿ-1].
   µ        New monadic chain. Argument: A
    Ṁ       Maximum; yield 2ⁿ-1.
     :      Divide 2ⁿ-1 by each k in A.
      «     Dyadic minimum; yield min((2ⁿ-1)/k, k) for each k in A.
        ¹   Identity; yield A.
       ạ    Absolute difference; yield k - min((2ⁿ-1)/k, k) for each k in A.
         S  Take the sum.

Dennis

Posted 2017-06-08T05:43:54.587

Reputation: 196 637

MATL, 10 9 bytes

Wqt:&*R<z

Try it online!

This tries all possible pairs. It runs out of memory in the online interpreter for input exceeding 12.

Explanation

W      % Implicitly input N. Push 2^N ('^' denotes power)
q      % Subtract 1: gives 2^N-1
t:     % Duplicate, range: pushes [0 1 2 ... 2^N-1]
&*     % Matrix of all pair-wise products
R      % Upper triangular part (including diagonal)
<      % Less-than comparison; element-wise. This gives true for products
       % that are greater than 2^N-1
z      % Number of non-zeros- Implicitly display

Luis Mendo

Posted 2017-06-08T05:43:54.587

Reputation: 87 464

Brachylog, 21 bytes

;2↔^P>B≥Aℕ;B C×≥P∧C≜ᶜ

Try it online!

Leaky Nun

Posted 2017-06-08T05:43:54.587

Reputation: 45 011

You don't need to explicitly give the name A to that variable, saving one byte. – Fatalize – 2017-06-08T10:18:33.643

JavaScript (ES7), 70 65 60 bytes

n=>[...Array(k=2**n-1)].reduce(p=>p+=k<++i*i&&i-(k/i|0),i=0)

Test cases

let f =

n=>[...Array(k=2**n-1)].reduce(p=>p+=k<++i*i&&i-(k/i|0),i=0)

for(n = 1; n <= 16; n++) {
  console.log(n, f(n))
}

Arnauld

Posted 2017-06-08T05:43:54.587

Reputation: 111 334

05AB1E, 13 12 bytes

-1 byte thanks to Emigna

oDL<ã€{ÙP›_O

Try it online!

Explanation

oDL<ã€{ÙP›_O   Argument n
oD             2^n, push twice to the stack
  L<           List: [0 .. a]
    ã          Cartesian product with itself
     €{        Sort each element
       Ù       Uniquify
        P      Total product of each element
         ›_    Each element is greater or equal than 2^n
           O   Total sum

kalsowerus

Posted 2017-06-08T05:43:54.587

Reputation: 1 894

Just P is enough here. – Emigna – 2017-06-08T06:47:00.130

@Emigna it is, thanks. I will edit that – kalsowerus – 2017-06-08T06:48:41.867

Mathematica, 37 bytes

Sum[#-⌈#/a⌉~Max~a,{a,#-1}]&[2^#]&

Try it online at http://sandbox.open.wolframcloud.com. Mathematica does not have limit on integers, and this algorithm run in time 2ⁿ, so it is very slow for large n.

user202729

Posted 2017-06-08T05:43:54.587

Reputation: 14 620

Clojure, 78 bytes

#(count(for[l[(bit-shift-left 1 %)]a(range l)b(range a l):when(>=(* a b)l)]1))

NikoNyrh

Posted 2017-06-08T05:43:54.587

Reputation: 2 361

Actually, 13 bytes

╙;r⌠;R*i⌡M♀≥Σ

Try it online!

A literal implementation of the problem. Quite slow.

Leaky Nun

Posted 2017-06-08T05:43:54.587

Reputation: 45 011

13: ╙;r;∙♂S╔♂π♀≥Σ (minor edit to the version I posted in chat)

– Mego – 2017-06-08T08:31:37.420

@Mego I don't feel like copying your code. – Leaky Nun – 2017-06-08T08:35:47.240

PHP, 62 bytes

for($x=$n=2**$argn;$y=--$x;)for(;$y;)$x*$y--<$n?:$r++;echo+$r;

Try it online!

Jörg Hülsermann

Posted 2017-06-08T05:43:54.587

Reputation: 13 026

Python 2, 53 bytes

lambda n:sum(k-min(~-2**n/k,k)for k in range(1,2**n))

Try it online!

Dennis

Posted 2017-06-08T05:43:54.587

Reputation: 196 637

Jelly, 11 bytes

2*’©ŒċP€>®S

Try it online!

A literal implementation of the problem. Quite slow.

Leaky Nun

Posted 2017-06-08T05:43:54.587

Reputation: 45 011

Counting N-bit integer multiplication overflows

Rules

Test Cases

Answers

Python 2, 75 68 bytes

Jelly, 12 10 bytes

How it works

MATL, 10 9 bytes

Explanation

Brachylog, 21 bytes

JavaScript (ES7), 70 65 60 bytes

Test cases

05AB1E, 13 12 bytes

Explanation

Mathematica, 37 bytes

Clojure, 78 bytes

Actually, 13 bytes

PHP, 62 bytes

Python 2, 53 bytes

Jelly, 11 bytes