• Home
  • About Us
  • Contact Us
  • Privacy Policy
  • Special Offers
Business Intelligence Info
  • Business Intelligence
    • BI News and Info
    • Big Data
    • Mobile and Cloud
    • Self-Service BI
  • CRM
    • CRM News and Info
    • InfusionSoft
    • Microsoft Dynamics CRM
    • NetSuite
    • OnContact
    • Salesforce
    • Workbooks
  • Data Mining
    • Pentaho
    • Sisense
    • Tableau
    • TIBCO Spotfire
  • Data Warehousing
    • DWH News and Info
    • IBM DB2
    • Microsoft SQL Server
    • Oracle
    • Teradata
  • Predictive Analytics
    • FICO
    • KNIME
    • Mathematica
    • Matlab
    • Minitab
    • RapidMiner
    • Revolution
    • SAP
    • SAS/SPSS
  • Humor

Generation of Step Numbers

October 27, 2017   BI News and Info

I am working on Project Euler 178 but got stuck in trying to optimize my code. The following text comes from the problem:

Consider the number $ 45656$ .
It can be seen that each pair of consecutive digits of $ 45656$ has a difference of one.
A number for which every pair of consecutive digits has a difference of one is called a step number.
A pandigital number contains every decimal digit from $ 0$ to $ 9$ at least once.
How many pandigital step numbers less than $ 10^{40}$ are there?

I thought of computing the entirety of step numbers with less than $ 40$ digits and subsequently selecting the pandigital ones. The first way to generate these numbers that came to my mind was to define a function

Generate[Ls_] := Module[{F = First[Ls], L = Ls},
                        Which[F == 9,
                              Return[{Prepend[L, F - 1]}],
                              F == 0,                    
                              Return[{Prepend[L, F + 1]}],                       
                              F != 0 && F != 9,                                     
                              Return[{Prepend[L, F + 1], Prepend[L, F - 1]}
                             ]
                       ]

which takes in input a list of lists, for instance {{5}}, and returns a list of lists with a prepended digit that differs by one from the original one, in this case {{4,5},{6,5}}. The first two cases handle the case in which the digit is $ 0$ or $ 9$ . I’ll handle the problem with the first digit being zero later. From here, I thought of nesting this by defining another function

GenMap[Ls_] := Flatten[Map[Generate, Ls], 1]

that should be nested to obtain the result. For instance,

Startingfromfive = Nest[GenMap, {{5}}, 15]; 

would generate the list of digits of the various $ 15$ digit step numbers that end with the digit $ 5$ .

This solution is clearly non optimal and has performance problems, due to the fact that the number of lists that need to be handled grows incredibly fast: Startingfromfive is a list of $ 22001$ lists of $ 15$ elements each. The computation time seems to be growing exponentially, as can be seen from the following plot:

ListPlot[Table[First[Timing[Nest[GenMap, {{5}}, n];]], {n, 1, 20}]]

y0q4s Generation of Step NumbersNest[GenMap, {{5}}, n] “>

My machine gets up to $ n=25$ in about $ 3$ minutes, showing the unfeasability for $ n=40$ with the aforementioned method. I tried compiling the function, but it doesn’t seem to show a substantial improvement.

Can this code be optimized or do I need to use a completely different approach?

Let’s block ads! (Why?)

Recent Questions – Mathematica Stack Exchange

Generation, Numbers, Step
  • Recent Posts

    • Ba’al comes to CPAC, Ted Cruz jokes about his Cancun trip
    • Optimizing data migration/integration with Power Platform
    • AI Weekly: Biden calls for $37 billion to address chip shortage
    • NOT WHAT THEY MEANT BY “BUILDING ON THE BACKS OF….”
    • Why Healthcare Needs New Data and Analytics Solutions Before the Next Pandemic
  • Categories

  • Archives

    • February 2021
    • January 2021
    • December 2020
    • November 2020
    • October 2020
    • September 2020
    • August 2020
    • July 2020
    • June 2020
    • May 2020
    • April 2020
    • March 2020
    • February 2020
    • January 2020
    • December 2019
    • November 2019
    • October 2019
    • September 2019
    • August 2019
    • July 2019
    • June 2019
    • May 2019
    • April 2019
    • March 2019
    • February 2019
    • January 2019
    • December 2018
    • November 2018
    • October 2018
    • September 2018
    • August 2018
    • July 2018
    • June 2018
    • May 2018
    • April 2018
    • March 2018
    • February 2018
    • January 2018
    • December 2017
    • November 2017
    • October 2017
    • September 2017
    • August 2017
    • July 2017
    • June 2017
    • May 2017
    • April 2017
    • March 2017
    • February 2017
    • January 2017
    • December 2016
    • November 2016
    • October 2016
    • September 2016
    • August 2016
    • July 2016
    • June 2016
    • May 2016
    • April 2016
    • March 2016
    • February 2016
    • January 2016
    • December 2015
    • November 2015
    • October 2015
    • September 2015
    • August 2015
    • July 2015
    • June 2015
    • May 2015
    • April 2015
    • March 2015
    • February 2015
    • January 2015
    • December 2014
    • November 2014
© 2021 Business Intelligence Info
Power BI Training | G Com Solutions Limited