Fooling around with the Collatz Sequence

Spent some time working on https://projecteuler.net/problem=14

It was fun, and I produced:

Crunching Collatz Sequence...go make some coffee
 Number 13 also has same number of terms as previous record
New record of 18 iterations found for 14
 Number 15 also has same number of terms as previous record
New record of 21 iterations found for 18
 Number 19 also has same number of terms as previous record
New record of 24 iterations found for 25
New record of 112 iterations found for 27
New record of 113 iterations found for 54
 Number 55 also has same number of terms as previous record
New record of 116 iterations found for 73
New record of 119 iterations found for 97
New record of 122 iterations found for 129
New record of 125 iterations found for 171
New record of 128 iterations found for 231
 Number 235 also has same number of terms as previous record
New record of 131 iterations found for 313
New record of 144 iterations found for 327
New record of 145 iterations found for 649
 Number 654 also has same number of terms as previous record
 Number 655 also has same number of terms as previous record
 Number 667 also has same number of terms as previous record
New record of 171 iterations found for 703
New record of 179 iterations found for 871
New record of 182 iterations found for 1161
New record of 183 iterations found for 2223
 Number 2322 also has same number of terms as previous record
 Number 2323 also has same number of terms as previous record
New record of 209 iterations found for 2463
New record of 217 iterations found for 2919
New record of 238 iterations found for 3711
New record of 262 iterations found for 6171
New record of 268 iterations found for 10971
New record of 276 iterations found for 13255
New record of 279 iterations found for 17647
 Number 17673 also has same number of terms as previous record
New record of 282 iterations found for 23529
New record of 308 iterations found for 26623
New record of 311 iterations found for 34239
 Number 35497 also has same number of terms as previous record
New record of 324 iterations found for 35655
New record of 340 iterations found for 52527
New record of 351 iterations found for 77031
New record of 354 iterations found for 106239
New record of 375 iterations found for 142587
New record of 383 iterations found for 156159
New record of 386 iterations found for 216367
New record of 443 iterations found for 230631
New record of 449 iterations found for 410011
New record of 470 iterations found for 511935
New record of 509 iterations found for 626331
New record of 525 iterations found for 837799

The record number of terms was 525, Produced by number 837799
RUN FINISHED; exit value 0; real time: 320ms; user: 0ms; system: 300ms

This felt good, so I bumped the target number up to 1 billion and got


Crunching Collatz Sequence...go make some coffee
 Number 13 also has same number of terms as previous record
New record of 18 iterations found for 14
 Number 15 also has same number of terms as previous record
New record of 21 iterations found for 18
 Number 19 also has same number of terms as previous record
New record of 24 iterations found for 25
New record of 112 iterations found for 27
New record of 113 iterations found for 54
 Number 55 also has same number of terms as previous record
New record of 116 iterations found for 73
New record of 119 iterations found for 97
New record of 122 iterations found for 129
New record of 125 iterations found for 171
New record of 128 iterations found for 231
 Number 235 also has same number of terms as previous record
New record of 131 iterations found for 313
New record of 144 iterations found for 327
New record of 145 iterations found for 649
 Number 654 also has same number of terms as previous record
 Number 655 also has same number of terms as previous record
 Number 667 also has same number of terms as previous record
New record of 171 iterations found for 703
New record of 179 iterations found for 871
New record of 182 iterations found for 1161
New record of 183 iterations found for 2223
 Number 2322 also has same number of terms as previous record
 Number 2323 also has same number of terms as previous record
New record of 209 iterations found for 2463
New record of 217 iterations found for 2919
New record of 238 iterations found for 3711
New record of 262 iterations found for 6171
New record of 268 iterations found for 10971
New record of 276 iterations found for 13255
New record of 279 iterations found for 17647
 Number 17673 also has same number of terms as previous record
New record of 282 iterations found for 23529
New record of 308 iterations found for 26623
New record of 311 iterations found for 34239
 Number 35497 also has same number of terms as previous record
New record of 324 iterations found for 35655
New record of 340 iterations found for 52527
New record of 351 iterations found for 77031
New record of 354 iterations found for 106239
New record of 375 iterations found for 142587
New record of 383 iterations found for 156159
New record of 386 iterations found for 216367
New record of 443 iterations found for 230631
New record of 449 iterations found for 410011
New record of 470 iterations found for 511935
New record of 509 iterations found for 626331
New record of 525 iterations found for 837799
New record of 528 iterations found for 1117065
 Number 1126015 also has same number of terms as previous record
New record of 531 iterations found for 1501353
 Number 1564063 also has same number of terms as previous record
New record of 557 iterations found for 1723519
New record of 560 iterations found for 2298025
New record of 563 iterations found for 3064033
New record of 584 iterations found for 3542887
New record of 597 iterations found for 3732423
New record of 613 iterations found for 5649499
New record of 665 iterations found for 6649279
New record of 686 iterations found for 8400511
New record of 689 iterations found for 11200681
New record of 692 iterations found for 14934241
New record of 705 iterations found for 15733191
New record of 706 iterations found for 31466382
 Number 31466383 also has same number of terms as previous record
New record of 745 iterations found for 36791535
New record of 950 iterations found for 63728127
New record of 951 iterations found for 127456254
 Number 127456255 also has same number of terms as previous record
New record of 954 iterations found for 169941673
New record of 957 iterations found for 226588897
New record of 965 iterations found for 268549803
New record of 966 iterations found for 537099606
 Number 537099607 also has same number of terms as previous record
New record of 987 iterations found for 670617279

The record number of terms was 987, Produced by number 670617279

RUN FINISHED; exit value 0; real time: 7m 6s; user: 760ms; system: 7m 4s

This was single-core on a Virtual machine running on a core i5 (sandybridge).

I am not sure I want to test what 4 billion looks like without finding a way to use more than one thread.

I don’t think the answer is wrong, but I might have made a mistake I don’t yet realize 🙂

x-cycle: insert a rotating X-Forwarded-For Header

I made a pretty simple chrome extension that allows you to configure a list of IP addresses, as well as a target host and it will insert an X-Forwarded-For header into the requests for the target host, and switch to the next IP in your configured list after about 6 requests.

This was useful to me when testing our a Web Application Firewall.

I have attempted to publish it in the Chrome Store several times, and the experience is just horrible. It gets published, then without reason, it gets taken down until I raise a support ticket. One day later, it gets published again with no explanations or apologies offered, and the cycle repeats again.

If you’re in luck, it may be available in the chrome store here: https://chrome.google.com/webstore/detail/x-cycle/bnlmhngacoghehikmhlcmpkbbnjdifca

Otherwise, you can download the latest copy I have hosted on my server: https://nucco.org/files/x-cycle.crx

If you care for this sort of thing, the sha1sum of the current file on my server should be:

c436ae78256a212851ee862e19fe51d08eab0049 *x-cycle.crx

Enjoy.

Walled Gardens need Improvement

I came face to face with “The Man” recently, and lost hopelessly.

You see, I spent two weekends working on a relatively basic Chrome Extension that I find useful in my day job; I often have to test a Web App Firewall, and usually you need to simulate traffic from multiple different source clients. The easiest way to do this for HTTP is to use the X-Forwarded-For (XFF) header, and configure your WAF to trust it. So, I thought, If i made an extension to automatically switch the XFF header, it would take some tedium out of this process.

I spent a bit of time on the Eloquent Javascript and the Chrome Developer Documentation, and over two weekends, came up with a slightly configurable and reasonably usable extension that allows you to inject XFF header into requests to a target server you configure. I called it “x-cycle“.

Feeling proud of my accomplishment, I push this to the Chrome Store  as a Developer Tool (paid a $5 verification fee in the process).

I spend the next 12 hours eagerly searching for my extension in the Chrome Web Store, hoping that my first ever extension would show up. After frustration with not finding it, I decide to go to my Chrome Developer Dashboard and check. “At least one of your items has been removed from the store because it did not comply with our policies or terms of service.” Huh? No email, no notification, and no specification of which terms I have violated, and very little I can do about it. 

Nobody will get to use my extension, unless I distribute it manually, and Chrome already makes it near impossible to distribute an extension outside of the Chrome Store, so, I won’t get much traction there, regardless of how much I think people with my kind of job would find this tool useful.

I understand more vividly why walled gardens can be a problem. Previously, I have always preferred Android to iOS because I felt like Google didn’t do too much to dictate what kind of software I can use on my phone compared to Apple, but looking at Chrome, it seems like I never considered the fact that Chrome has become a walled Garden, and one that badly needs to improve its engagement at that.

If you take down someone’s work, you need to at least explain why, so that they can work on resolving it. I get the distinct feeling that some Reviewer just saw “X-Forwarded-For”, googled it, and saw it as a way to “mask” your IP address, and thought “Oh No! Hacking Tool!!” and took it down. This would be a real shame.

Any experienced web admin knows that you don’t trust X-Forwarded-For, unless it was set by a device that you control, thus there is limited scope for abuse of this extension, even for people who are intent on mischief. The policy for trusting XFF is that you strip whatever you received, and then inject the value that you are going to trust. Someone who tests a WAF is both in control of the client and the web-server, and can configure it to trust this header, and this is what makes this extension useful in my view.

I have submitted a support ticket to some Google Support service that took some Googling to find hoping I would get back a more actionable response whenever they do get round to it.

Until then, twiddling thumbs and wondering whether the “open” web we so proudly proclaim is not really just a walled garden with tremendous power in the hands of the people who make web browsers. It is probably little wonder then that practically all browsers are free of charge; they trade the cost for the users, which in turn amplify the power of the browser vendor. They can then hold advertisers, publishers and developers to ransom. Hmmm.