N个自然数列中的特殊对

Question

给你一个自然数N，它代表序列[1,2...N]。我们必须从这个序列中确定满足给定条件的对 (x,y) 的数量。

1 <= x <= y <= N
前 x-1 个数字的总和（即 [1,2,3..x-1] 的总和）= 从 x+1 到 y 的数字总和（即 [x+1...y] 的总和）

示例：-
如果 N = 3 只有 1 对 (x=1,y=1) 其中 (x-1 个数字的总和) = 0 = (x+1 到 y 的总和)
任何其他对，如 (1,2)、(1,3) 或 (2,3) 都不满足这些属性。所以答案是 1，因为只有一对。

另一个例子：-
如果 N=10，对于 (6,8) 对，我们可以看到 x-1 个数字的总和，即 [1,2,3,4,5] = 15 = 从 x+1 到 y 的数字总和，即 [7,8]，也是另一个这样的对将是（1,1）。不存在其他这样的对，所以在这种情况下，答案是 2。

我们如何处理和解决此类问题以找到这样一个序列中的对数？

到目前为止我已经能够推断出的其他事情：-

Condition	Answer	Pairs
If 1<=N<=7	1	`{(1,1)}`
If 8<=N<=48	2	`{(1,1),(6,8)}`
If 49<=N<=287	3	`{(1,1),(6,8),(35,49)}`
If 288<=N<=1680	4	-

我试过了，但无法在这些数字中找到任何模式或任何类似的东西。
另外，1<=N<=10^16

Answer 1

--编辑--

由 OEIS 提供（link 在评论中）：您可以使用以下公式找到 y 的第 k 个值：( (0.25) * (3.0+2.0*(2**0.5))* *k).floor

这给了我们 O(log k) 中的第 k 个值。前几个结果：

1
8
49
288
1681
9800
57121
332928
1940449
11309768
65918161
384199200
2239277041
13051463048
76069501249
443365544448
2584123765441
15061377048200
87784138523761
511643454094368
2982076586042447
17380816062160312
101302819786919424
590436102659356160
3441313796169217536
20057446674355949568
116903366249966469120
681362750825442836480
3971273138702690287616
23146276081390697054208
134906383349641499377664
786292024016458181771264
4582845760749107960348672
26710782540478185822224384
155681849482119992477483008
907380314352241764747706368

请注意，连续数字的比率很快接近 5.828427124746。给定 n 的值，取 n 底数 5.828427124746 的对数。答案将是接近此日志的整数。

例如，假设 n = 1,000,000,000。然后 log(n, 5.8284271247461) = 11.8。答案大概是12，不过我们可以查一下邻居来确定。

11:    65,918,161
12:   384,199,200
13: 2,239,277,041

已确认。

-- 结束编辑--

这里有一些 ruby 代码可以执行此操作。想法是有两个指针并根据需要增加 x 或 y 的指针。我正在使用 s(n) 来计算总和，尽管这可以通过仅保持运行总计而无需乘法来完成。

def s(n)
  return n*(n+1)/2
end
  
  
def f(n)
  count = 0
  x = 1
  y = 1
  while y <= n do
    if s(x-1) == s(y) - s(x)
      count += 1 
      puts "(#{x}, #{y})"
    end
    if s(x-1) <= s(y) - s(x)
      x += 1
    else
      y += 1
    end
  end
end

这是前几对：

(1, 1)
(6, 8)
(35, 49)
(204, 288)
(1189, 1681)
(6930, 9800)
(40391, 57121)
(235416, 332928)
(1372105, 1940449)
(7997214, 11309768)
(46611179, 65918161)

N个自然数列中的特殊对

Special Pairs in N natural number sequence

arrays

algorithm

math

numbers

sum