+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: C, C++, & Obj-C (https://sinister.li/Forum-C-C-Obj-C)
+--- Thread: C++ - Euler 463 (/Thread-C-Euler-463)
RE: C++ - Euler 463 - ArkPhaze - 03-17-2014
I got values ;p
Code:
S(1) = 1
S(3) = 5
S(7) = 21
S(15) = 85
S(31) = 341
S(63) = 1365
S(127) = 5461
S(255) = 21845
S(511) = 87381
S(1023) = 349525
S(2047) = 1398101
S(4095) = 5592405
S(8191) = 22369621
S(16383) = 89478485
S(32767) = 357913941
S(65535) = 1431655765
S(131071) = 5726623061
S(262143) = 22906492245
S(524287) = 91625968981
S(1048575) = 366503875925
S(2097151) = 1466015503701
S(4194303) = 5864062014805
S(8388607) = 23456248059221
S(16777215) = 93824992236885
S(33554431) = 375299968947541
S(67108863) = 1501199875790165
S(134217727) = 6004799503160661
S(268435455) = 24019198012642645
S(536870911) = 96076792050570581
S(1073741823) = 384307168202282325
S(2147483647) = 1537228672809129301
S(4294967295) = 6148914691236517205
S(8589934591) = 24595658764946068821
S(17179869183) = 98382635059784275285
S(34359738367) = 393530540239137101141
S(68719476735) = 1574122160956548404565
S(137438953471) = 6296488643826193618261
S(274877906943) = 25185954575304774473045
S(549755813887) = 100743818301219097892181
S(1099511627775) = 402975273204876391568725
S(2199023255551) = 1611901092819505566274901
S(4398046511103) = 6447604371278022265099605
S(8796093022207) = 25790417485112089060398421
S(17592186044415) = 103161669940448356241593685
S(35184372088831) = 412646679761793424966374741
S(70368744177663) = 1650586719047173699865498965
S(140737488355327) = 6602346876188694799461995861
S(281474976710655) = 26409387504754779197847983445
S(562949953421311) = 105637550019019116791391933781
S(1125899906842623) = 422550200076076467165567735125
S(2251799813685247) = 1690200800304305868662270940501
S(4503599627370495) = 6760803201217223474649083762005
S(9007199254740991) = 27043212804868893898596335048021
S(18014398509481983) = 108172851219475575594385340192085
S(36028797018963967) = 432691404877902302377541360768341
S(72057594037927935) = 1730765619511609209510165443073365
S(144115188075855871) = 6923062478046436838040661772293461
S(288230376151711743) = 27692249912185747352162647089173845
S(576460752303423487) = 110768999648742989408650588356695381What I NEED is in between S(576460752303423487) and S(288230376151711743). My code works though.
RE: C++ - Euler 463 - invisal - 03-17-2014
Well, another pattern that can reduce the gap
RE: C++ - Euler 463 - ArkPhaze - 03-17-2014
I think you're forgetting part of that notation. I'll take a look at this tomorrow though, it's about time I get off the computer for today. I have work tomorrow, and I'm already a bit groggy.
RE: C++ - Euler 463 - invisal - 03-17-2014
I found another clue, but I think I need to go and take some fresh air.
It will help me figure more.
RE: C++ - Euler 463 - ArkPhaze - 03-18-2014
I've noticed something here for f(n):
Code:
1
1 3 1
1 5 3 7 1
1 9 5 11 3 13 7 15 1
1 17 9 19 5 21 11 23 3 25 13 27 7 29 15 31 1RE: C++ - Euler 463 - invisal - 03-18-2014
Well, I found another pattern
Crap. It is wrong.
RE: C++ - Euler 463 - invisal - 03-18-2014
Okay, I have solved this one.
@ArkPhaze
Spoiler:
S(3^37) = 74400999745652642791290200808981553
I will explain the logic behind the code later.
Code:
import math
def S(n):
# I have proof for this one, but
# too long to explain here.
# ------------------------------
# S(2^n+1 - 1) = 1 - 4^n / -3
power = int(math.ceil(math.log(n, 2)))
if (2**power == n):
return ((1 - 4**power) / -3) + 1
# I have proof this one
# -------------------------------
# S(2^n) = 1
base = ((1 - 4**(power-1)) / -3) + 1
n = n - 2**(power-1)
# Calculate the reminding S(2^n + 1 -> N)
# Since F(n) is a reverse bit of n, all we
# need to do is couting the number of bit on
# each slot and apply the reverse multiplier
# -------------------------------
power -= 1
bit = [0] * power
for i in range(power - 1, -1, -1):
if (n & 2**i > 0):
bit[i] += (n % 2**i) + 1
for j in range(i - 1, -1, -1):
bit[j] += 2**(i-1)
base = base + n
for i in range(0, power):
base = base + 2**(power - i) * bit[i]
return baseRE: C++ - Euler 463 - invisal - 03-18-2014
Let prove that F(N) is a reverse bit of N by Strong Induction.
Base Case:
- F(1) = 1, and 1 is the reverse bit of 1. (TRUE)
Inductive Step:
- Let n be integer that 0 < 4n + 2 <= N
- Let [f(n)] be the binary representation of f(n), we may also write
[10f(n)] to mean that binary [10] following by binary of f(n) or
[n0] to mean binary of "n" following by binary [0]
- Assume by strong induction that F(1), F(2), ..., F(N) holds
Let experiment case by case
- N = 2n - 1, then F(N+1) = F(2n) = F(n) = F([n0]) = [0f(n)] = f(n)
Because leading 0's binary does not add any value.
- N = 4n, then F(N+1) = F(4n + 1) = 2F(2n + 1) - F(n).
(Eq.1): F(4n + 1) = F([n01]) = [10F(n)]
(Eq.2): 2F(2n + 1) - F(n) = [10(2F(n))] - F(n) = [10F(n)]
(Eq.1) and (Eq.2) equals therefore it is true.
- N = 4n + 2, then F(N+1) = F(4n + 3) = 3F(2n + 1) - 2F(n)
(Eq.3): F(4n + 3) = F([n11]) = [11F(n)]
(Eq.4): 3F(2n + 1) - 2F(n) = [11(3F(n))] - 2F(n) = [11F(n)]
(Eq.3) and (Eq.4) equals therefore it is true
By strong induction, F(N) holds for every N >= 1.